P15679 [ICPC 2024 Jakarta R] Buggy DFS
题目描述
你正在研究一种名为**深度优先搜索 (DFS)** 的图遍历算法。然而，由于一个错误，你的算法与标准的 DFS 略有不同。以下是你的 **Buggy DFS (BDFS)** 算法，假设图有 $N$ 个节点（编号从 $1$ 到 $N$）。
```
BDFS():
令 S 为一个空栈
令 FLAG 为一个大小为 N 的布尔数组，初始值全为 false
令 counter 为一个整数，初始化为 0
将 1 压入 S
当 S 不为空时：
将 S 的栈顶元素弹出到 u
FLAG[u] = true
对于 u 的每个邻居 v（按升序）：
counter = counter + 1
如果 FLAG[v] 为 false：
将 v 压入 S
返回 counter
```
你意识到这个错误导致算法比标准 DFS 更慢，这可以通过函数 BDFS() 的返回值来研究。为了研究该算法的行为，你想通过构造一个**无向简单图**来创建一些测试用例，使得函数 BDFS() 返回 $K$，或者判断这是否不可能。
输入格式
一行，包含一个整数 $K$（$1 \leq K \leq 10^9$）。
输出格式
如果不可能构造一个无向简单图使得函数 BDFS() 返回 $K$，则在一行中输出 `-1 -1`。
否则，按以下格式输出图。第一行包含两个整数 $N$ 和 $M$，分别表示图中的节点数和无向边数。接下来的 $M$ 行，每行包含两个整数 $u$ 和 $v$，表示连接节点 $u$ 和节点 $v$ 的一条无向边。你可以以任意顺序输出边。该图必须满足以下约束：
- $1 \leq N \leq 32\,768$
- $1 \leq M \leq 65\,536$
- 对于所有边，$1 \leq u, v \leq N$。
- 图是一个简单图，即没有重边和自环。
注意，你不需要最小化节点数或边数。可以证明，如果存在一个图使得 BDFS() 的返回值为 $K$，那么一定存在一个满足上述所有约束的图。如果有多个解，你可以输出其中任意一个。
说明/提示
**样例输入/输出 #1 的解释**
左侧的图描述了本样例的输出。右侧的图描述了本样例的另一个有效解。
:::align{center}
:::
**样例输入/输出 #3 的解释**
下图描述了本样例的输出。
:::align{center}
:::
翻译由 DeepSeek V3.2 完成