#P18473. Turn on the Light 2
Turn on the Light 2
Turn on the Light 2
Lux et Veritas(光明与真知)
备受期待的 Universal Cup 决赛即将到来!小青鱼正在准备比赛场地。为了让场地绚丽夺目,他打算悬挂一些灯泡。
小青鱼有 根电线,打算用它们连接 个灯泡。每根电线连接两个不同的灯泡,全部灯泡必须构成一个连通块。任意两个灯泡之间至多有一根电线直接相连,每个灯泡连接的电线数不能超过 。
连接好后,小青鱼想点亮其中一些灯泡。亮灯会发热,因此直接相连的两个灯泡不能同时点亮。另一方面,也不能出现一个没有点亮的灯泡,且与它直接相连的所有灯泡也都没有点亮。
对于一种接线方案,可以有多种满足要求的亮灯方案。给定 ,请使用全部 根电线,确定灯泡数 及接线方式,使满足要求的亮灯方案数量最大。 由你自行选择。
输入格式
第一行一个整数 (),表示测试数据组数。
每组数据一行两个整数 (,)。
输出格式
对每组数据:
第一行输出一个整数 (),表示最多能有多少种满足要求的亮灯方案。
第二行输出一个整数 (),表示灯泡数。
接下来输出 行,每行两个整数 (,),表示一根直接连接这两个灯泡的电线。输出必须满足上述连通、无重边及度数限制,且实际亮灯方案数应恰为最优值 。
样例
输入:
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
样例说明
图中灰色圆圈代表点亮的灯泡。第一组数据的两种亮灯方案如下:

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