#P18424. Inverse Problem

Inverse Problem

Inverse Problem

考虑下面的问题:给定一棵有 nn 个顶点(n≥1n\ge1)的树,即一个连通、无环的无向图。请使用 nn 种颜色对顶点染色,求合法染色方案数。

若任意两个距离不超过两条边的不同顶点具有不同颜色,则染色合法。两种染色不同,当且仅当至少有一个顶点在两种染色中的颜色不同。方案数可能很大,因此只需给出它模 109+710^9+7 的余数。

你的任务是解决它的逆问题:给定 1≤r≤109+61\le r\le10^9+6,找出一棵顶点数最少的树,使上面问题的答案恰为 rr。可以证明,对这个范围中的每个 rr,都至少存在一棵满足要求的树。

如果顶点数最少的树有多棵,输出其中任意一棵。输出的树有多少个顶点,就必须使用同样数量的颜色计算染色方案数。

输入格式

第一行包含整数 tt(1≤t≤101\le t\le10),表示测试用例数。

接下来 tt 行,每行包含一个整数。第 ii 行为 rir_i,满足 1≤ri≤109+61\le r_i\le10^9+6。保证所有 rir_i 两两不同。

输出格式

输出 tt 个块,第 ii 块回答第 ii 个测试用例。

每个块第一行输出一个正整数 nin_i,表示所构造树的顶点数,且这个顶点数必须是所有符合 rir_i 的树中的最小值。

接下来的 ni−1n_i-1 行,每行输出两个整数 ai,j,bi,ja_{i,j},b_{i,j}(1≤ai,j,bi,j≤ni1\le a_{i,j},b_{i,j}\le n_i),表示连接这两个顶点的一条边。顶点编号为 1,2,…,ni1,2,\ldots,n_i。输出必须确实构成一棵树。

若有多棵最优树,可以输出任意一棵。当 ni=1n_i=1 时,这个块只有顶点数一行,没有边。

完整原样例

输入:

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

样例最后一个测试用例中,所给树的合法染色方案数为 15099494401509949440,模 109+710^9+7 后为 509949433509949433。