Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
本サイトのこの部分にお気づきでしょうか。
これらの番号は、どのページからどのページへも少ないクリック数で到達できるように、なおかつ各ページのリンク数が多くなりすぎないように配慮して選ばれています。 この問題では、似たようなことを 1 ページあたり リンク 2 つ で実現していただきましょう。
すぬけ君は、1 から N までの番号が振られた N ページからなるサイトを作りました。 あなたには、各 i (1 \leq i \leq N) について 2 つの整数 a_i, b_i (1 \leq a_i, b_i \leq N) を選び、ページ i にページ a_i へのリンクとページ b_i へのリンクを貼ることで、以下の制約を満たしていただきます。
- どのページから他のどのページへも、リンクを 10 回以下クリックすることで到達可能でなければならない。
この問題の制約の下で、これが常に可能であることは証明可能です。
制約
- 1 \leq N \leq 1000
入力
入力は標準入力から以下の形式で与えられる。
N
出力
答えを以下の形式で出力せよ。
a_1 \ b_1 : a_N \ b_N
複数通りの答えが考えられる場合は、そのどれを出力してもよい。
入力例 1
1
出力例 1
1 1
すぬけ君は 1 ページだけの見事なサイトを作りました。 自分自身へのリンクも 2 つあります。
入力例 2
3
出力例 2
2 3 1 3 1 2
ここでは、どのページからどのページへも直接のリンクで到達できます。
Score : 500 points
Problem Statement
Have you noticed this part of AtCoder website?
Here the numbers are carefully chosen so that we can jump from any page to any page in small number of steps, while each page doesn't contain too many links. In this task you are asked to do a similar thing with only two links on each page!
Snuke made a website with N pages numbered 1 through N. For each i (1 \leq i \leq N), choose two integers a_i and b_i (1 \leq a_i, b_i \leq N), and add two links on Page i: a link to Page a_i and a link to Page b_i. The website must satisfy the following constraint:
- You must be able to jump from any page to any other page by clicking at most 10 links.
Under the constraints of the problem, we can prove that this is always possible.
Constraints
- 1 \leq N \leq 1000
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer in the following format:
a_1 \ b_1 : a_N \ b_N
In case there are multiple possible answers, print any.
Sample Input 1
1
Sample Output 1
1 1
Snuke made an excellent website with only one page. It even contains two links to itself!
Sample Input 2
3
Sample Output 2
2 3 1 3 1 2
Here we can jump from any page to any other page by a direct link.