Problem:


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.



Sample input:
3


Sample output:
Yes
1 2
2 3
3 4
4 5
5 6

Submission status: Wrong Answer

Solution code:
n = int(input())
if n != 1 and 2 ** 17 - 1 & n == n:
    print('Yes')
    for i in range(1,2 * n):
        print(str(i) + ' ' + str(i + 1))
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import math
import fractions

n = list(map(int, input().split()))
n = n[0]

if(n%3==0 and False):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import math
import fractions

n = list(map(int, input().split()))
n = n[0]

if(n%3==0):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())

sum = 0
for i in range(1,n-1):
    sum ^= i

if sum != 1:
    print('No')
else:
    for i in range(1,(2 * n)):
        print("{} {}".format(i, i+1))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans ^= i
    if not ans:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n,m = LI()

    return

#C
def C():
    n = I()
    if n == 1:
        print("No")
        quit()
    p = [(1<<i) for i in range(1,100)]
    if n+1 in p:
        print("Yes")
        for i in range(1,2*n):
            print(i,i+1)
        quit()
    if n in p:
        print("No")
        quit()
    ans = []
    for i in range(1,3):
        ans.append((i,i+1))
    ans.append((3,n+1))
    for i in range(1,3):
        ans.append((i+n,i+n+1))
    u = 1
    d = 1
    for i in range(2,n//2+n%2):
        ans.append((u,2*i))
        ans.append((d,2*i+1))
        ans.append((2*i,2*i+n+1))
        ans.append((2*i+1,2*i+n))
        u = 2*i+n+1
        d = 2*i+n

    if n%2:
        print("Yes")
        for i,j in ans:
            print(i,j)
    else:
        ans.append((n-1,n))
        ans.append((2,2*n))
        print("Yes")
        for i,j in ans:
            print(i,j)
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 14 20:47:36 2019

@author: ctiuser
"""

N = int(input())

flg = 0
ans = []
for i in range(N):
    flg ^= (i+1)
    ans.append([i+1,i+2])
    ans.append([i+1+N,i+2+N])

if flg == 0:
    print('Yes')
    for i in range(2*N-1):
        print(' '.join(map(str,ans[i])))

else:
    print('No')

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**6)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]


N = read()

if N % 4 != 3:
  print("No")
  exit()

print("Yes")
for i in range(2*N - 1):
  print(i+1, i+2)

Submission status: Wrong Answer

Solution code:
n = int(input())
if n != 1:
    print('Yes')
    for i in range(1,2 * n):
        print(str(i) + ' ' + str(i + 1))
else:
    print('No')

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans ^= i
    if not ans:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n,m = LI()

    return

#C
def C():
    n = I()
    if n == 1:
        print("No")
        quit()
    if n%2 == 0:
        print("No")
        quit()
    p = [(1<<i)-1 for i in range(1,100)]
    if n in p:
        print("Yes")
        for i in range(1,2*n):
            print(i,i+1)
        quit()
    ans = []
    for i in range(1,3):
        ans.append((i,i+1))
    ans.append((3,n+1))
    for i in range(1,3):
        ans.append((i+n,i+n+1))
    u = 1
    d = 1
    for i in range(2,n//2+1):
        ans.append((u,2*i))
        ans.append((d,2*i+1))
        ans.append((2*i,2*i+n+1))
        ans.append((2*i+1,2*i+n))
        u = 2*i+n+1
        d = 2*i+n
    print("Yes")
    for i,j in ans:
        print(i,j)
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

if math.floor(math.log(N, 2)) == math.log(N, 2):
    print("No")
    exit()
else:
    print("Yes")

i = 1
print(N+1, N+2)
while i < N:
    if i+2 <= N:
        print(1, i+1)
        print(i+1, i+2)
        print(1, i+2+N)
        print(i+2+N, i+1+N)
        i += 2
    else:
        print(i-1, i+1)
        print(N+3, i+1+N)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

if math.floor(math.log(N, 2)) == math.log(N, 2):
    print("No")
    exit()
else:
    print("Yes")

i = 1
print("{} {}".format(N+1, N+2))
while i < N:
    if i+2 <= N:
        print("1 {}".format(i+1))
        print("{} {}".format(i+1, i+2))
        print("1 {}".format(i+2+N))
        print("{} {}".format(i+2+N, i+1+N))
        i += 2
    else:
        print("{} {}".format(i-1, i+1))
        print("{} {}".format(N+3, i+1+N))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
if n%4==3:
    print("Yes")
    for i in range(n*2-1):
        print(str(i+1)+" "+str(i+2))
else:
    l=[0 for i in range(1000000000)]

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

k = 2

while pow(2,k)-1 <= n:
    if pow(2,k)-1 == n:
        print("Yes")
        for i in range(2*n-1):
            print(i+1, i+2)
        exit()

print("No")

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/agc035/tasks/agc035_c

全ての対の頂点に関して、パス上の重みのxorが自分に等しい
1から順に求めていくことを考える

A,Bの関係を考える
木なので、片方のパス上にあればいい→片方にのみ含ませることも、両方に含ませることも可能

1をいい感じに使って構築できないか？

101-100-1-101-100
みたいに、1の位だけ違う数字をまとめて処理すればいい感じになる
もう一つの1は、どっかの葉につけておけばおk
これで、Nが奇数かつ1でない場合は全て構築可能！！

偶数の時は？ 2,4みたいな場合は自明にダメ
6は？
001 010 011 100 101 110
xorで110になるのは010と100

101-100-1-010-011
    |     |
    110   100

→分からんけどとりあえず提出

偶数でも可能な場合がある…
(N+i)-(N+i+1)- -(i)-(i+1)
とする

"""
import sys
N = int(input())

if N == 1:
    print ("No")

elif N % 2 == 1:
    print ("Yes")

    for i in range(2,N+1,2):
        print (1,i)
        print (i,i+1)
        print (1,i+1+N)
        print (i+1+N,i+N)

    print (N+1,3)

else:

    a = None
    b = None

    for i in range(1,N):
        if N ^ i < N:
            a = i
            b = N ^ i

    if a == None:
        print ("No")
        sys.exit()
    
    print ("Yes")
    for i in range(2,N,2):
        print (i,i+1)
        print (N+i,N+i+1)

        #1につけていく
        if i not in (a,b) and i+1 not in (a,b):
            print (1,i)
            print (1,N+i+1)

    pa = a^1
    pb = b^1

    #print ("===")

    print (N+1,a)
    print (a,b)
    print (N,a)
    print (b,2*N)
    print (1,pa)

    print (1,a+N)
    print (pa+N,pb+N)

Submission status: Accepted

Solution code:
n,k,i=int(input()),1,2
p=print
if-n&n==n:p("No");exit()
p("Yes",v:=n+1,3)
while i<n:p(1,i,i,i+1,1,v+i,v+i,n+i);i+=2;k<<=k*2<v
if~n&1:p(n,v+k,n+n,n^k)

Submission status: Accepted

Solution code:
n,k,i=int(input()),1,2
v=n+1
p=print
if-n&n==n:p("No");exit()
p("Yes",v,3)
while i<n:p(1,i,i,i+1,1,v+i,v+i,n+i);i+=2;k<<=k*2<v
if~n&1:p(n,v+k,n+n,n^k)

Submission status: Accepted

Solution code:
n,k,i=int(input()),1,2
v=n+1
p=print
if-n&n==n:p("No");exit()
p("Yes",v,3)
while i<n:p(1,i,i,i+1,1,v+i,v+i,n+i);i+=2;k*=1+(k*2<v)
if~n&1:p(n,v+k,n+n,n^k)

Submission status: Accepted

Solution code:
n,k,i=int(input()),1,2
v=n+1
p=print
while k*2<v:k*=2
if-n&k:p("No");exit()
p("Yes",v,3)
while i<n:p(1,i,i,i+1,1,v+i,v+i,n+i);i+=2
if~n&1:p(n,v+k,n+n,n^k)

Submission status: Accepted

Solution code:
n,k=int(input()),1
while k*2<=n:k*=2
p=print
if n==k:p("No");exit()
p("Yes",v:=n+1,3)
i=2
while i<n:p(1,i,i,i+1,1,v+i,v+i,n+i);i+=2
if~n&1:p(n,v+k,n+n,n^k)

Submission status: Accepted

Solution code:
n,k=int(input()),1
while k*2<=n:k*=2
p=print
if n==k:p("No");exit()
p("Yes",v:=n+1,3)
i=2
while i<n:p(1,i,i,i+1,1,v+i,v+i,n+i);i+=2
if~n&1:p(n,n+k+1,n+n,n^k)

Submission status: Accepted

Solution code:
n,k=int(input()),1
while k*2<=n:k*=2
p=print
if n==k:p("No");exit()
p("Yes",v:=n+1,3)
for i in range(2,n,2):p(1,i,i,i+1,1,v+i,v+i,n+i)
if~n&1:p(n,n+k+1,n+n,n^k)

Submission status: Accepted

Solution code:
n=int(input())
p,r=print,range
if n&-n==n:p("No");exit(0)
p("Yes")
if n==3:p(1,2);p(2,3);p(3,4);p(4,5);p(5,6);exit(0)
k=1
while k*2<n:k*=2
for i in r(k-2):p(i+1,i+2)
p(k-1,n+1)
for i in r(k-2):p(n+i+1,n+i+2)
p(n+k,n+1);p(n+k+1,k)
for i in r(n-k):p(n+i+1,n+k+i+1);p(n+k+i,k+i+1)

Submission status: Accepted

Solution code:
N=int(input())
if (N&-N)==N:
  print('No')
  exit()
print('Yes')
P=[[] for i in range(2*N)]
X=1
while 2*X-1<=N:
  X*=2
X-=1
for i in range(X-1):
  P[i].append(i+1)
  P[N+i].append(N+i+1)
P[X-1].append(N)
while X+2<=N:
  P[X].append(X+1)
  P[0].append(X+1)
  P[0].append(X+N)
  P[X+N].append(X+N+1)
  X+=2
if X!=N:
  X=N&(-N)
  P[X-1].append(N-1)
  if X==2:
    P[N-X].append(2*N-1)
  else:
    P[2*N-X-1].append(2*N-1)
for i in range(len(P)):
  for j in range(len(P[i])):
    print(i+1,P[i][j]+1)

Submission status: Accepted

Solution code:
N=int(input())
if N&(N-1)==0:
    print("No")
else:
    print("Yes")
    if N%2==1:
        k=N//2
        for i in range(1,k+1):
            print(2*i,2*i+1)
            print(2*i+1,1)
            print(1,2*i+N)
            print(2*i+N,2*i+1+N)
        print(1+N,2)
    else:
        k=N//2-1
        for i in range(1,k+1):
            print(2*i,2*i+1)
            print(2*i+1,1)
            print(1,2*i+N)
            print(2*i+N,2*i+1+N)
        print(1+N,2)
        n=N.bit_length()-1
        a=2**n
        b=N+1-a
        print(N,a+N)
        print(2*N,b)

Submission status: Accepted

Solution code:
n = int(input())
nn = n
f = lambda x, y: x + y * nn
g = lambda x: x if x % 2 == 1 else x + nn

# 2の累乗はむり
b = bin(n)
if b.count('0') == len(b) - 2:
    print('No')
    exit(0)

ret = [
    [f(1, 0), f(2, 0)],
    [f(2, 0), f(3, 0)],
    [f(3, 0), f(1, 1)],
    [f(1, 1), f(2, 1)],
    [f(2, 1), f(3, 1)],
]

if n % 2 == 0:
    p = 2 ** (len(b) - 3)
    q = n ^ 1 ^ p
    ret.append([g(p), f(n, 0)])
    ret.append([g(q), f(n, 1)])
    n -= 1

# nは奇数
while n > 3:
    ret.append([f(n - 1, 0), f(n, 0)])
    ret.append([f(n, 0), f(1, 1)])
    ret.append([f(1, 1), f(n - 1, 1)])
    ret.append([f(n - 1, 1), f(n, 1)])
    n -= 2

print('Yes')
for x, y in ret:
    # x = x if x <= nn else x - nn
    # y = y if y <= nn else y - nn
    print(x, y)

Submission status: Accepted

Solution code:
n=int(input());p=print;b=1<<n.bit_length()-1
if n==b:p("No");exit()
p("Yes");p(n+1,n+2)
for i in range(3,n+1,2):p(1,i);p(1,i-1);p(i,n+i-1);p(i-1,n+i)
if~n&1:p(b,n);p(n^1^b,n+n)

Submission status: Accepted

Solution code:
n=int(input());p=print;b=1<<(n.bit_length()-1)
if n==b:p("No");exit()
p("Yes");p(n+1,n+2)
for i in range(3,n+1,2):p(1,i);p(1,i-1);p(i,n+i-1);p(i-1,n+i)
if~n&1:p(b,n);p(n^1^b,n+n)

Submission status: Accepted

Solution code:
n = int(input())
if n & (-n) == n: print('No'); exit(0)
m = n - 1 + n % 2
print('Yes')
l = [(3, 2), (2, 1), (1, 3+n), (3+n, 2+n), (2+n, 1+n)]
for x, y in l:
  print(x, y)
for i in range(4, m+1):
  print(i, 1)
  print((i^1) + n, i)
if n != m:
  t = n & (-n)
  print(n, t)
  print(t^1^n, n*2)

Submission status: Accepted

Solution code:
import sys

N=int(input())
n=N
while n%2==0:
    n//=2
if n==1:
    print("No")
    sys.exit()

m=0
while True:
    m+=1
    if 2**m>N:
        m-=1
        break

ans=[]
if N%2==0:
    ans.append([N,2**m])
    ans.append([2*N,(N-2**m+1+N)])

ans.append([N+1,3])
for i in range(1,(N-1)//2+1):
    num=2*i
    ans.append([1,num])
    ans.append([num,num+1])
    ans.append([1,N+num+1])
    ans.append([N+num+1,N+num])
    
print("Yes")
for u in ans:
    print(*u)

Submission status: Accepted

Solution code:
n = int(input())
b = 1 << (n.bit_length()-1)
if n - b == 0:
  print("No")
else:
  print("Yes")
  print(1, 2)
  print(2, 3)
  print(3, n+1)
  print(n+1, n+2)
  print(n+2, n+3)
  for i in range(4, n, 2):
    print(i, i+1)
    print(i+n, i+n+1)
    print(1+n, i+n)
    print(1+n, i+1)
  if (~n)&1:
    print(n, b+n)
    a = n ^ b ^ 1
    print(n+n, a)

Submission status: Accepted

Solution code:
n = int(input())
for i in range(100):
  if n == 1<<i:
    print("No")
    exit()
print("Yes")
l = (n+1).bit_length()-1
ans = []
for i in range(2,2**l):
  ans.append((i-1,i))
  ans.append((n+i-1,n+i))
ans.append((2**l-1,n+1))
m = n-1+(n%2)
for i in range(2**l+1,m+1):
  ans.append((i-1,i))
  ans.append((n+i-1,n+i))
if n != 2**l-1:
  if (m+1)%4 == 0:
    ans.append((1,2**l))
    ans.append((m,n+2**l))
  else:
    ans.append((m+n,1))
    ans.append((1,2**l))
if n>m and (m+1)%4 == 0:
  ans.append((n-2**l,n))
  ans.append((2**l,2*n))
elif n>m:
  ans.append((2,n))
  ans.append((2*n,2*n-1))
for edge in ans:
  print(*edge)

Submission status: Accepted

Solution code:
N = int(input())

last = -1
tmp = N
ct = 0
while tmp > 0:
    if last == -1:
        if tmp&1:
            last = ct
    tmp = tmp>>1
    ct += 1

if 1 << last == N:
    print("No")
elif last == 0:
    print("Yes")
    for i in range(2, N+1):
        if i&1:
            print(1, i)
            print(i, N+i-1)
        else:
            print(1, i)
            print(i, N+i+1)
    print(N+3, N+1)
else:
    print("Yes")
    for i in range(2, N):
        if i&1:
            print(1, i)
            print(i, N+i-1)
        else:
            print(1, i)
            print(i, N+i+1)
    print(N+3, N+1)
    k = 1 << last
    l = N ^ (k+1)
    print(k, N)
    print(l, 2*N)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    k = N.bit_length()

    if 1<<(k-1) == N:
        print('No')
        exit()
    print('Yes')
    if N == 3:
        for i in range(1, 6):
            print(i, i+1)
        exit()

    N0 = 1<<(k-1)
    e = [(N0-1, N+1)]
    for i in range(1, N0-1):
        e.append((i, i+1))
        e.append((i+N, i+1+N))

    if N%2 == 0:
        v = N ^ N0
        e.append((N, v))
        e.append((N*2, N0))
        for i in range(N0, N):
            if i % 2 == 0:
                e.append((i, v))
                e.append((i + N, i+N+1))
            else:
                e.append((i, i - 1))
                e.append((i + N, v + 1))
    else:
        for i in range(N0, N + 1):
            if i % 2 == 0:
                e.append((i, 2))
                e.append((i + N, i + 1 + N))
            else:
                e.append((i, i - 1))
                e.append((i + N, 3 + N))
    for edge in e:
        print(*edge)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline       
N = int(readline())

ans = 'Yes' if -N&N != N else 'No'
print(ans)
if ans == 'Yes':
    Edge = []
    
    for i in range(2, N-(N%2 == 0)+1):
        Edge.append((1, i))
        if not i&1:
            Edge.append((i, N+i+1))
            Edge.append((i+1, N+i))
    Edge.append((N+1, N+3))
    if not N&1:
        Edge.append(((-N&N)+1, N))
        Edge.append((N^(-N&N), N+N))
    print('\n'.join([' '.join(map(str, e)) for e in Edge]))

Submission status: Accepted

Solution code:
n=int(input())
s=len(bin(n))-2
if 2**(s-1)==n:
  print("No")
elif n==3:
  print("Yes")
  for i in range(1,6):
    print(i,i+1)
else:
  print("Yes")
  print(2**(s-1)-1,1+n)
  for i in range(1,2**(s-1)-1):
    print(i,i+1)
    print(i+n,i+n+1)
  print(2**(s-1),2**(s-1)+1)
  print(2**(s-1)+1+n,1)
  print(2**(s-1),1)
  print(2**(s-1)+n,2**(s-1)+1+n)
  for i in range(2**(s-1)+2,n+1):
    print(i,i-1+n)
    print(i+n,i-2**(s-1))

Submission status: Accepted

Solution code:
import sys

N = int(input())

if (N & -N) == N:
    print('No')
    sys.exit()

N2 = N if N%2 else N-1
anss = []
for i in range(2, N2+1):
    anss.append((1, i))
for i in range(2, N2+1):
    anss.append((i, (i^1)+N))
anss.append((2+N, 1+N))

if N%2 == 0:
    N2 = N+1
    k = 1<<(N2.bit_length()-1)
    anss.append((N, k))
    anss.append((2*N, N2^k))

print('Yes')
print('\n'.join(map(lambda x: str(x[0])+' '+str(x[1]), anss)))

Submission status: Accepted

Solution code:
N = int(input())
b = N.bit_length()
if 2 ** (b - 1) == N:
    print('No')
    exit()

ans = [(N + 2, N + 1), (N + 2, 3), (3, 1), (1, 2), (2, 3 + N)]
for i in range(4, N, 2):
    ans.append((1, i))
    ans.append((1, i + 1))
    ans.append((i, N + i + 1))
    ans.append((i + 1, N + i))

if N % 2 == 0:
    for i in range(30, -1, -1):
        if N > 2 ** i:
            a = 2 ** i
            break
    b = N - a + 1
    ans.append((N, a))
    ans.append((b, 2 * N))
    

print('Yes')
for a, b in ans:
    print(a, b)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()

two_power = [pow(2, i) for i in range(30)]

# 2べき判定
if n in two_power:
    print("No")

# 1とNまでつなげる
else:
    edges = []
    for i in range(2, (n+1) - (n+1)%2):
        edges.append((1, i))

# 2からNまでとN+2から2Nまでつなげる (偶数ならN-1まで)
    for i in range(2, (n+1) - (n+1)%2):
        if i % 2:
            edges.append((i, n + i - 1))
        else:
            edges.append((i, n + i + 1))

# N+2とN+1つなげる
    edges.append((n+1, n+2))

# 偶数なら最上位ビットにNを、それ以外+1に2Nをつなげる
    if n%2 == 0:
        edges.append((1 << (n.bit_length() - 1), n))
        edges.append((n - (1 << (n.bit_length()) - 1) + 1, 2*n))

    print("Yes")
    for edge in edges:
        print(*edge)

Submission status: Accepted

Solution code:
import sys
n = int(input())
if n < 3:
	print("No")
else:
	#print("Yes")
	ans = []
	for i in range(2, n, 2):
		ans.append([1, i])
		ans.append([i, i+1])
		ans.append([1, n+i+1])
		ans.append([n+i+1, n+i])
	ans.append([3, n+1])
	if n%2 == 0:
		for i in range(1, n):
			if (n+1)^i < n:
				if i%2 == 0:
					ans.append([i, n])
					ans.append([((n+1)^i) + n, 2*n])
				else:
					ans.append([(n+1)^i, n])
					ans.append([n+i, 2*n])
				break
		else:
			print("No")
			sys.exit()
	print("Yes")
	for a in ans:
		print(*a)

Submission status: Accepted

Solution code:
N = int(input())

if N & (N-1) == 0:
  print("No")
  exit()

print("Yes")
print(1, 2)
print(2, 3)
print(3, N+1)
print(N+1, N+2)
print(N+2, N+3)

for i in range(4, N, 2):
  print(i, i+1)
  print(i+1, N+1)
  print(N+1, N+i)
  print(N+i, N+i+1)

if N % 2 == 0:
  print(N, N-1)
  x = N^(N-1)^1
  if x % 2 == 0:
    print(N+x, 2*N)
  else:
  	print(x, 2*N)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
t = n
while t > 0 and t % 2 == 0:
    t //= 2
ans = (t != 1)
print(['No', 'Yes'][ans])
if not ans:
    exit()
print(1, 2)
for i in range(2, n, 2):
    print(i, i + 1)
    print(i + 1, n + 1)
    print(n + 1, n + i)
    print(n + i, n + i + 1)
if n % 2 == 0:
    nob = len(bin(n)[2:])
    a = 1 << (nob - 1)
    b = (n + 1) ^ a
    a = n + a if a % 2 == 0 else a
    b = n + b if b % 2 == 0 else b
    print(n, a)
    print(b, 2 * n)

Submission status: Accepted

Solution code:
import sys
import math

input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())

def getlist():
    return list(map(int, input().split()))

n = getN() #22

dig_num = math.floor(math.log2(n + 1))  # 5
# print(dig_num)
sen_end = 2 ** (dig_num) - 1  # 15

if 2 ** (dig_num) == n or n == 1:
    print("No")
    sys.exit(0)
else:
    print("Yes")

for i in range(sen_end - 1):
    print(i+1, i+2)  # 1-2, 2-3, ..., 14-15
    print(i+1+n, i+2+n)  # 23-24, 24-25, ..., 36-37

print(n + 1, sen_end)

uni_end = n
if n % 2 == 0:
    uni_end -= 1  # 21

for i in range((uni_end - sen_end) // 2):  # 3 times
    print(1, sen_end + i * 2 + 1)  # 1-16
    print(1, sen_end + i * 2 + 2 + n)  # 1-39
    print(sen_end + i * 2 + 1 + n, sen_end + i * 2 + 2 + n)  # 38-39
    print(sen_end + i * 2 + 1, sen_end + i * 2 + 2)  # 16-17

if n % 2 == 0:
    one_count = 0
    for idx, digit in enumerate(bin(n)[2:]):
        # print(digit, one_count)
        if one_count == 0:
            # print(digit)
            if digit == "1":
                one_count += 1
        else:
            if digit == "1":
                one_goal = dig_num - idx  # second "1" from upper digit
                break

    if one_goal != 1:
        print(n, 2**one_goal)
        print(2*n, n - 2**one_goal)

    else:
        print(n, 2 ** one_goal)
        print(2 * n, 2 * n - 2 ** one_goal + 1)

Submission status: Accepted

Solution code:
N = int(input())

M = N
while M % 2 == 0 :
    M //= 2
    
if M == 1 or N < 3 :
    print('No')
else :
    print('Yes')
    print(3, 1)
    print(1, 2)
    print(2, 3 + N)
    print(3 + N, 1 + N)
    print(1 + N, 2 + N)
        
    for i in range(4, N, 2) :
        print(1, i + 1)
        print(i + 1, i)
        print(1, N + i)
        print(N + i, N + i + 1)
        
    if N % 2 == 0 :
        i = 1
        while True :
            if N >> i & 1 :
                break
            i += 1
        print((1 << i) + 1, N)
        print(2 * N - (1 << i), 2 * N)

Submission status: Accepted

Solution code:
import sys

N=int(input())
NOSET=set([1<<i for i in range(50)])

if N in NOSET:
    print("No")
    sys.exit()

print("Yes")
print(1,2)
print(1,3)
print(2,3+N)
print(3,2+N)
print(1+N,2+N)

t=(N+1)//2*2
for i in range(4,t,2):
    print(1,i)
    print(1,i+1)
    print(i,i+1+N)
    print(i+1,i+N)
    
if N%2==0:
    N_head = 1<<(N.bit_length()-1)
    print(N,N_head)
    print(N*2,N^N_head^1)

Submission status: Accepted

Solution code:
def is_2power(n: int)->bool:
    a = 1
    while a < n:
        a <<= 1
    return a == n


def skolem_xor_tree(N: int)->list:
    if is_2power(N):
        return []

    res = [
        (1, 2),
        (2, 3),
        (3, N+1),
        (N+1, N+2),
        (N+2, N+3),
    ]

    for a in range(4, N+(N % 2), 2):
        res.append((1, a))
        res.append((a, a+1))

        res.append((1, N+a+1))
        res.append((N+a+1, N+a))

    if N % 2 == 0:
        a = N ^ 1
        b = None
        for i in range(2, N):
            if (a ^ i) < N:
                a = a ^ i
                b = i
                break

        if not b:
            raise Exception()

        if a < N and a % 2 == 1:
            a += N

        if b < N and b % 2 == 1:
            b += N

        res.append((a, N))
        res.append((b, N+N))

    return res


if __name__ == "__main__":
    N = int(input())

    ans = skolem_xor_tree(N)
    if ans:
        print('Yes')
        for a, b in ans:
            print(a, b)
    else:
        print('No')

Submission status: Accepted

Solution code:
n = int(input())
if n < 3 or format(n - 1, "b").count("0") == 0:
    print("No")
    exit()
else:
    print("Yes")
for i in range(1, 3):
    print(i, i + 1)
    print(i + n, i + 1 + n)
print(1, 3 + n)

for i in range(5, n + 1, 2):
    print(1, i - 1)
    print(i - 1, i)
    print(1, i + n)
    print(i + n, i - 1 + n)

if not n % 2:
    a = 1 << (len(format(n + 1, "b")) - 1)
    b = (n + 1) ^ a
    a = a + n if a % 2 else a
    b = b + n if b % 2 else b
    print(a, n)
    print(b, 2 * n)

Submission status: Accepted

Solution code:
n=int(input())
p=print
if n in [2**i for i in range(32)]:
 p("No")
 exit()
p("Yes")
p(n+1,n+2)
for i in range(3,n+1,2):
 p(1,i)
 p(1,i-1)
 p(i,n+i-1)
 p(i-1,n+i)
if n%2==0:
 u=1<<(n.bit_length()-1)
 l=n^1^u
 p(u,n)
 p(l,n+n)

Submission status: Accepted

Solution code:
n = int(input())
pow2s = [2**item for item in range(32)]
if n in pow2s:
    print("No")
    exit()
print("Yes")
print(n+1, n+2)
for i in range(3, n+1, 2):
    print(1, i)
    print(1, i - 1)
    print(i, n + i - 1)
    print(i - 1, n + i)
if n % 2 == 0:
    upper = 1 << (n.bit_length() - 1)
    lower = n ^ 1 ^ upper
    print(upper, n)
    print(lower, n + n)

Submission status: Accepted

Solution code:
N = int(input())

def beki(n):
    return all(b == '0' for b in bin(n)[3:])

if beki(N):
    print('No')
else:
    print('Yes')
    print(1, 2)
    for i in range(2, N, 2):
        print(i, i+1)
        print(i+N, i+1+N)
        print(N+1, i+1)
        print(N+1, i+N)
    if N % 2 == 0:
        a = 2 ** (len(bin(N)[2:]) - 1)
        b = N ^ a ^ 1
        print(a+N, N)
        print(b, N*2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int):
    k = 1
    while k < N:
        k *= 2
    if N == k:
        print(NO)
        return
    print(YES)

    if N % 2 == 0:
        n = N - 1
        even = True
    else:
        n = N
        even = False

    for i in range(2, n+1):
        if i % 2 == 0:
            print(1, i)
            print(N+i+1, N+i)
        else:
            print(i, i-1)
            print(N+i, 1)
    print(3, N+1)
    if even:
        k //= 2
        print(N, k)
        a = N ^ k ^ 1
        print(a + N, N * 2)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(n):
    if n < 3:
        print('No')
        return
    d, m = divmod(n, 4)
    l = d * 4
    if m == 3:
        d += 1
        l += 4
    ans = ['{} {}'.format(x, y) for x, y in ((1, 2), (2, 3), (3, 1 + n), (1 + n, 2 + n), (2 + n, 3 + n))]

    if bin(l).count('1') == 1:
        if m == 0:
            print('No')
            return
        if m < 3:
            ans.extend('{} {}'.format(x, y) for x, y in ((1, l), (l, l + 1), (1, l + n + 1), (l + n + 1, l + n)))
            if m == 2:
                ans.extend('{} {}'.format(x, y) for x, y in ((2, l + 2), (l + n + 1, l + n + 2)))
            m = 3

    for i in range(4, l, 4):
        ans.extend('{} {}'.format(x, y) for x, y in (
            (i, i + 1), (i + 1, i + 2), (i + 2, i + 3), (i + 3, i + n),
            (i + n, i + n + 1), (i + n + 1, i + n + 2), (i + n + 2, i + n + 3)))

    if m == 3:
        for i in range(4, l, 4):
            ans.append('{} {}'.format(1, i))
        print('Yes')
        print('\n'.join(ans))
        return

    min_k = k = l & -l
    prev = 1
    connected = set()
    while k < l:
        if k & l:
            ans.append('{} {}'.format(prev, k))
            connected.add(k)
            prev = k
        k <<= 1

    for i in range(4, l, 4):
        if i in connected:
            continue
        ans.append('{} {}'.format(1, i))

    # print(*ans, sep='\n')
    # print('--')

    ans.append('{} {}'.format(l, min_k))
    ans.append('{} {}'.format(l + n, prev))

    if m >= 1:
        ans.append('{} {}'.format(l + 1, 1))
        ans.append('{} {}'.format(l + 1 + n, prev))
    if m >= 2:
        ans.append('{} {}'.format(l + 2, 1))
        ans.append('{} {}'.format(l + 2 + n, prev + 2))

    assert len(ans) == 2 * n - 1

    print('Yes')
    print('\n'.join(ans))


n = int(input())
solve(n)

Submission status: Accepted

Solution code:
n=int(input())
if n<=2 or n==4:
  print("No")
elif n==3:
  print("Yes")
  for i in range(5):
    print(i+1,i+2)
elif n%2==0:
  nn=n.bit_length()
  if n==2**(nn-1):
    print("No")
  else:
    print("Yes")
    print(1,2)
    print(2,3)
    print(3,n+1)
    print(n+1,n+2)
    print(n+2,n+3)
    for i in range(4,n):
      print(n+1,i)
      if i%2==0:
        print(i,i+n+1)
      else:
        print(i,i+n-1)
    n1,n2=2**(nn-1),(n+1)-2**(nn-1)
    print(n1,n)
    print(n2,2*n)
else:
  print("Yes")
  print(1,2)
  print(2,3)
  print(3,n+1)
  print(n+1,n+2)
  print(n+2,n+3)
  for i in range(4,n+1):
    print(1,i)
    if i%2==0:
      print(i,i+n+1)
    else:
      print(i,i+n-1)

Submission status: Accepted

Solution code:
import math
 
N = int(input())
 
if math.floor(math.log(N, 2)) == math.log(N, 2):
    print("No")
    exit()
else:
    print("Yes")
 
i = 1
print(N+1, N+2)
for i in range(1, N, 2):
    if i+2 <= N:
        print(1, i+1)
        print(i+1, i+2)
        print(1, i+2+N)
        print(i+2+N, i+1+N)
    else:
        print(i-1, i+1)
        tmp = (i+1) ^ (i-1) 
        print(N+tmp+1, i+1+N)