#P17850. FLO
FLO
— 花卉杂交
你要培育出恰好有 片花瓣的花。最初只有两种花,花瓣数分别为 和 。
唯一的杂交方法是:选择两种已有的花,它们分别有 片花瓣,培育出花瓣数为
的新种类。允许两次选择同一种花,已有种类可以反复使用。
给定若干询问。它们共享同一个目标 ,但初始的 不同。对每个询问,判断能否得到目标种类;如果能,输出一个不超过 次杂交的方案。不要求操作次数最少。
输入格式
第一行是十进制整数 。
第二行一个整数 ,表示询问数。第三行一个整数 ,表示每个方案允许的最大操作次数。
接下来 行,每行两个整数 。
输出格式
按输入顺序分别回答各询问。
若无解,输出一行 -1。
若有解,输出两行:第一行给出操作次数 ;第二行给出 个种类编号,每两个数表示一次杂交使用的两种花。
初始 片花瓣的花编号为0, 片花瓣的花编号为1。第 次操作得到的新种类编号为 ;这次操作只能引用编号 ,允许两个编号相同。最后产生的编号 的花必须恰有 片花瓣。
保证只要存在方案,就存在不超过 次操作的方案。合法方案可能不唯一。
数据范围
,,,。
注意 有5001个十进制数字。
以下五个子任务各20分:
| 子任务 | 附加限制 |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 |
样例 1
输入:
97
3
100
9 13
13 22
5 7
输出:
1
0 1
-1
2
0 1 2 0