/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
整数 N が与えられます。1 から 2N までの番号がついた 2N 個の頂点を持つ木であって次の条件を満たすものが存在するか判定し、存在するならばその一例を示してください。
- 1 以上 N 以下の各整数 i について、頂点 i, N+i の重みが i であるとする。このとき、1 以上 N 以下の各整数 i について、頂点 i, N+i 間のパス上にある頂点 (両端を含む) の重みのビットごとの排他的論理和が i である。
制約
- 入力は全て整数
- 1 \leq N \leq 10^{5}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
問題文中の条件を満たす木が存在するならば Yes を、そうでなければ No を出力せよ。
その後、存在するならば続く 2N-1 行にそのような木の 2N-1 本の辺を以下の形式で出力せよ。
a_{1} b_{1}
\vdots
a_{2N-1} b_{2N-1}
ここで、各組 (a_i, b_i) は木に頂点 a_i, b_i を結ぶ辺が存在することを表す。辺は任意の順で出力して構わない。
入力例 1
3
出力例 1
Yes 1 2 2 3 3 4 4 5 5 6
- 出力例は以下のグラフを表します。
入力例 2
1
出力例 2
No
- 条件を満たす木が存在しません。
Score : 700 points
Problem Statement
You are given an integer N. Determine if there exists a tree with 2N vertices numbered 1 to 2N satisfying the following condition, and show one such tree if the answer is yes.
- Assume that, for each integer i between 1 and N (inclusive), Vertex i and N+i have the weight i. Then, for each integer i between 1 and N, the bitwise XOR of the weights of the vertices on the path between Vertex i and N+i (including themselves) is i.
Constraints
- N is an integer.
- 1 \leq N \leq 10^{5}
Input
Input is given from Standard Input in the following format:
N
Output
If there exists a tree satisfying the condition in the statement, print Yes; otherwise, print No.
Then, if such a tree exists, print the 2N-1 edges of such a tree in the subsequent 2N-1 lines, in the following format:
a_{1} b_{1}
\vdots
a_{2N-1} b_{2N-1}
Here each pair (a_i, b_i) means that there is an edge connecting Vertex a_i and b_i. The edges may be printed in any order.
Sample Input 1
3
Sample Output 1
Yes 1 2 2 3 3 4 4 5 5 6
- The sample output represents the following graph:
Sample Input 2
1
Sample Output 2
No
- There is no tree satisfying the condition.