← 返回题目列表

Codeforces · 1408/F

F. 两种不同

中文机器翻译题面 查看原题

给你一个整数$$$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$$$ 行中打印两个整数。在第 $$$i$$$ 行中打印 $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$)。

应满足声明中描述的条件。

如果存在多个答案,您可以打印其中任何一个。

示例

输入 #1

3

输出 #1

1
1 2

输入 #2

4

输出 #2

2
1 2
3 4

注意

在第一个示例中,执行唯一操作后,数组 $$$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)]$$$。它始终最多有两个不同的数字。