#P18473. Turn on the Light 2

Turn on the Light 2

Turn on the Light 2

Lux et Veritas(光明与真知)

备受期待的 Universal Cup 决赛即将到来!小青鱼正在准备比赛场地。为了让场地绚丽夺目,他打算悬挂一些灯泡。

小青鱼有 mm 根电线,打算用它们连接 nn 个灯泡。每根电线连接两个不同的灯泡,全部灯泡必须构成一个连通块。任意两个灯泡之间至多有一根电线直接相连,每个灯泡连接的电线数不能超过 dd。

连接好后,小青鱼想点亮其中一些灯泡。亮灯会发热,因此直接相连的两个灯泡不能同时点亮。另一方面,也不能出现一个没有点亮的灯泡,且与它直接相连的所有灯泡也都没有点亮。

对于一种接线方案,可以有多种满足要求的亮灯方案。给定 m,dm,d,请使用全部 mm 根电线,确定灯泡数 nn 及接线方式,使满足要求的亮灯方案数量最大。nn 由你自行选择。

输入格式

第一行一个整数 TT(1≤T≤2001\le T\le200),表示测试数据组数。

每组数据一行两个整数 m,dm,d(2≤m≤202\le m\le20,2≤d≤m2\le d\le m)。

输出格式

对每组数据:

第一行输出一个整数 ww(1≤w≤2m+11\le w\le2^{m+1}),表示最多能有多少种满足要求的亮灯方案。

第二行输出一个整数 nn(1≤n≤m+11\le n\le m+1),表示灯泡数。

接下来输出 mm 行,每行两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i),表示一根直接连接这两个灯泡的电线。输出必须满足上述连通、无重边及度数限制,且实际亮灯方案数应恰为最优值 ww。

样例

输入:

3
2 2
5 4
6 2

输出:

2
3
1 2
2 3
5
5
1 2
1 3
2 3
1 4
4 5
7
7
1 2
2 3
3 4
4 5
5 6
6 7

样例说明

图中灰色圆圈代表点亮的灯泡。第一组数据的两种亮灯方案如下:

原题第一组的两种亮灯方案

第二组数据的五种亮灯方案如下:

原题第二组的五种亮灯方案