CF1408F Two Different

给定一个整数 $n$。 你需要找到一组数对 $(x_1, y_1)$，$(x_2, y_2)$，…，$(x_q, y_q)$（$1 \leq x_i, y_i \leq n$），使其满足以下条件。 我们考虑一个函数 $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$（其中 $\mathbb{N}$ 表示正整数集合）。换句话说，$f$ 是一个对任意两个正整数返回一个正整数的函数。 我们构造一个数组 $a_1, a_2, \ldots, a_n$，初始时 $a_i = i$。 你需要进行 $q$ 次操作，在第 $i$ 次操作中： 1. 令 $t = f(a_{x_i}, a_{y_i})$（$t$ 是一个临时变量，仅用于接下来的两步赋值）； 2. 令 $a_{x_i} = t$； 3. 令 $a_{y_i} = t$。 也就是说，你需要同时将 $a_{x_i}$ 和 $a_{y_i}$ 都赋值为 $f(a_{x_i}, a_{y_i})$。注意，在整个过程中，对于固定的 $p$ 和 $q$，$f(p, q)$ 总是相同的。 最终，数组 $a$ 中最多只能有两种不同的数。 上述要求对于任意函数 $f$ 都必须成立。 请你找到任意一组满足条件的数对列表。数对的数量不得超过 $5 \cdot 10^5$。

一行一个整数 $n$（$1 \leq n \leq 15\,000$）。

第一行输出一个整数 $q$（$0 \leq q \leq 5 \cdot 10^5$），表示数对的数量。 接下来的 $q$ 行，每行输出两个整数，表示一组数对 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq n$）。 你输出的数对列表需要满足题目中的条件。 如果有多组答案，输出任意一组均可。

在第一个样例中，执行唯一的一次操作后，数组 $a$ 变为 $[f(a_1, a_2), f(a_1, a_2), a_3]$。此时数组中最多只有两种不同的数。 在第二个样例中，执行两次操作后，数组 $a$ 变为 $[f(a_1, a_2), f(a_1, a_2), f(a_3, a_4), f(a_3, a_4)]$。此时数组中最多只有两种不同的数。 由 ChatGPT 4.1 翻译