[R44E]路径数为K - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个整数 $K$，你需要构造一个有向无环图（DAG），且满足以下条件：

1. 该图的顶点编号为 $1$ 到 $n$，且点数 $n$ 不能超过 $50$，且图没有重边。

2. 从顶点 $1$ 出发到达顶点 $n$ 的不同路径数量恰好为 $K$。

如果有多种有向无环图满足条件，输出任意一种。

格式

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行包含一个整数 $K$，表示需要构造的目标路径数量。

输出格式

对于每组数据，输出你构造的图的信息：

第一行包含两个整数 $n$ 和 $m$，分别表示图的点数和边数。你需要保证 $2 \le n \le 50$。

接下来 $m$ 行，每行包含两个整数 $u, v$，表示存在一条从 $u$ 到 $v$ 的有向边。

样例

样例输入 #1

2
1
3

样例输出 #1

2 1
1 2
4 5
1 2
2 4
1 3
3 4
1 4

样例解释 #1

对于 $K=1$：

起点 $1$ 到终点 $2$ 只有一条路径：$1 \to 2$。

对于 $K=3$： 起点 $1$ 到终点 $4$ 的路径有：

1. $1 \to 2 \to 4$
2. $1 \to 3 \to 4$
3. $1 \to 4$ 共 $3$ 条。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$T\le$	$K\le$
$1$	$20$	$40$	$40$
$2$	$80$	$100$	$10^9$

对于 $100\%$ 的数据，$1 \le T \le 100$，$1 \le K \le 10^9$。