#P18424. Inverse Problem
Inverse Problem
Inverse Problem
考虑下面的问题:给定一棵有 个顶点()的树,即一个连通、无环的无向图。请使用 种颜色对顶点染色,求合法染色方案数。
若任意两个距离不超过两条边的不同顶点具有不同颜色,则染色合法。两种染色不同,当且仅当至少有一个顶点在两种染色中的颜色不同。方案数可能很大,因此只需给出它模 的余数。
你的任务是解决它的逆问题:给定 ,找出一棵顶点数最少的树,使上面问题的答案恰为 。可以证明,对这个范围中的每个 ,都至少存在一棵满足要求的树。
如果顶点数最少的树有多棵,输出其中任意一棵。输出的树有多少个顶点,就必须使用同样数量的颜色计算染色方案数。
输入格式
第一行包含整数 (),表示测试用例数。
接下来 行,每行包含一个整数。第 行为 ,满足 。保证所有 两两不同。
输出格式
输出 个块,第 块回答第 个测试用例。
每个块第一行输出一个正整数 ,表示所构造树的顶点数,且这个顶点数必须是所有符合 的树中的最小值。
接下来的 行,每行输出两个整数 (),表示连接这两个顶点的一条边。顶点编号为 。输出必须确实构成一棵树。
若有多棵最优树,可以输出任意一棵。当 时,这个块只有顶点数一行,没有边。
完整原样例
输入:
4
2
360
1
509949433
一种合法输出:
2
1 2
5
1 2
2 3
3 4
3 5
1
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
样例最后一个测试用例中,所给树的合法染色方案数为 ,模 后为 。