P16310 [ICPC 2023 Jinan R] 开灯 2

:::epigraph Lux et Veritas （光明与真知） ::: 受期待的宇宙杯（Universal Cup）决赛即将来临！小青鱼正在忙着准备比赛的场地。为了使得场地炫彩夺目，小青鱼计划悬挂一些电灯泡。 小青鱼有 $m$ 根电线，并打算用这些电线连接 $n$ 个灯泡。每根电线需要连接两个不同的灯泡，并使得所有灯泡形成一个连通块。为了安全起见，任意两个灯泡之间最多只能有一根电线把它们直接连起来，且每个灯泡最多只能连接 $d$ 根电线。 连接好灯泡后，小青鱼想要点亮其中一些灯泡。考虑到亮着的灯泡会产生热量，让两个相邻的灯泡同时点亮可能会有危险。因此，如果两个灯泡之间直接通过电线连接，则它们不能同时被点亮。另一方面，他也不想让灯光太少，所以他不希望看到一个灯泡没亮，且与之直接连接的所有灯泡也都没亮。 小青鱼非常好奇在这些限制条件下，能有多少种不同的方案来点亮这些灯泡。此外，他还想找到一种连接所有灯泡的方式，使得点亮灯泡的方案数量最大化。 给定整数 $m$ 与 $d$，您的目标是协助小青鱼来确定使用所有 $m$ 根电线连接 $n$ 个灯泡的最佳方式，最大化点亮灯泡的方案数。请注意，您需要自行确定 $n$ 的值。

有多组测试数据。第一行输入一个整数 $T$（$1 \leq T \leq 200$）表示测试数据组数，对于每组测试数据： 第一行输入两个整数 $m$ 与 $d$（$2 \le m \le 20$，$2 \le d \le m$）。

对于每组测试数据： 第一行输出一个整数 $w$（$1 \leq w \leq 2^{m+1}$），表示最多可以有多少种方法点亮灯泡。 第二行输出一个整数 $n$（$1 \leq n \leq m+1$），表示小青鱼需要使用的灯泡数量。 接下来输出 $m$ 行，其中第 $i$ 行输出两个由单个空格分隔的整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n, u_i \neq v_i$），表示一条连接第 $u_i$ 个灯泡与第 $v_i$ 个灯泡的电线。

我们用涂色的圆圈代表点亮的灯泡。 对于第一组样例数据，$2$ 种点亮灯泡的方案如下图所示。 :::align{center}  ::: 对于第二组样例数据，$5$ 种点亮灯泡的方案如下图所示。 :::align{center}  :::