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: Accepted

Solution code:
N = int(input())
def judge(N):
  if N <= 2:
    print('No')
    return
  for k in range(2, 18):
    if 2 ** k > N + 1:
       break
  K = 2 ** (k - 1) - 1
  if N - K == 1:
    print('No')
    return
  print('Yes')
  if N % 2:
    for i in range(1, K):
      print('{} {}'.format(i, i + 1))
      print('{} {}'.format(i + N, i + 1 + N))
    print('{} {}'.format(K, N + 1))
    if K < N:
      for i in range(K + 1, N + 1):
        print('{} {}'.format(i, 1 if i % 2 else i + 1))
        print('{} {}'.format(i + N, 1 if i % 2 == 0 else i - 1 + N))
  else:
    for i in range(K + 1, N):
      print('{} {}'.format(i, 1 if i % 2 else i + 1))
      print('{} {}'.format(i + N, 1 if i % 2 == 0 else i - 1 + N))
    m = N ^ (K + 1)
    print('{} {}'.format(N, m + N))
    print('{} {}'.format(m + N, K + 1))
    print('{} {}'.format(K + 1, 2 * N))
    P = [i for i in range(2, K + 1)]
    P.pop(P.index(m))
    print('{} {}'.format(2 * N - 1, P[0]))
    for i, p in enumerate(P[:-1]):
      print('{} {}'.format(p, P[i + 1]))
      print('{} {}'.format(p + N, P[i + 1] + N))
    print('{} {}'.format(P[-1], m))
    print('{} {}'.format(P[-1] + N, m + N))
    print('{} {}'.format(K + 1, N + 1))
judge(N)

Submission status: Accepted

Solution code:
N = input()

if N<=2:
  print "No"
  exit(0)

for i in range(100):
  if 2**i==N:
    print "No"
    exit(0)

print "Yes"

print 1, 3
print 3, 2
print 2, N+1
print N+1, N+3
print N+3, N+2

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

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

Submission status: Accepted

Solution code:
n = input()

if bin(n).count('1') == 1:
    print "No"
    exit(0)

print "Yes"

for i in xrange(1, 3):
    print i, i + 1
    print i+n, i+n+1

print 3, 1 + n

for i in xrange(4, n, 2):
    print i, i + 1
    print i + 1, 1
    print 1, i + n
    print i + n, i + 1 + n

if n % 2 == 0:
    print n, n - 1
    print (n ^ (n - 1) ^ 1) + n, n + n

Submission status: Accepted

Solution code:
N = int(input())

res = 'Yes'

k = 0

while 2 ** (k + 1) - 1 <= N:
    k += 1

K = 2 ** k - 1


if N == 1:
    res = 'No'
if N == K + 1:
    res = 'No'
# print(N, K)

if N % 2 == 0:
    M = N - 1
else:
    M = N
if (M - K) % 4 == 0 and M > K:
    L = M - 2
else:
    L = M

P = N - K
if P % 2 == 0:
    P = 2

print(res)

if res == 'Yes':
    line = list(range(1, K + 1))
    line.remove(P)
    line = [1, P] + line[1:]
    
    for i in range(K - 1):
        print(line[i], line[i + 1])
    print(line[-1], N + 1)
    for i in range(K - 1):
        print(N + line[i], N + line[i + 1])
    if L > K:
        print(1, K + 1)
        for i in range(K + 1, L):
            print(i, i + 1)
        for i in range(K + 1, L):
            print(N + i, N + i + 1)
        print(N + L, 1)
    if M > L:
        print(N + 1, M - 1)
        print(M - 1, M)
        print(N + M - 1, N + M)
        print(N + M, N + 1)
    if N > M:
        print(N, K + 1)
        print(N + N, P)

Submission status: Accepted

Solution code:
N = int(input())
n = 1<<N.bit_length()-1
if N == n:
    print("No")
else:
    print("Yes")
    # print(n)
    ANS = []
    if N % 2:
        for i in range(1, n-1):
            ANS.append((i, i+1))
        ANS.append((n-1, N+1))
        for i in range(1, n-1):
            ANS.append((i+N, i+N+1))
        for i in range(0, N-n, 2):
            ANS.append((1+N, i+n))
            ANS.append((i+n, i+n+1))
            ANS.append((1+N, i+n+1+N))
            ANS.append((i+n+1+N, i+n+N))
    else:
        a, b, c = N-2, N-1, N
        X = [i for i in range(1, n) if i != a^c] + [c, a]
        # print("X =", X)
        for i in range(n-1):
            ANS.append((X[i], X[i+1]))
        ANS.append((X[n-1], X[0]+N))
        for i in range(n-1):
            ANS.append((X[i]+N, X[i+1]+N))
        for i in range(0, N-n-3, 2):
            ANS.append((1+N, i+n))
            ANS.append((i+n, i+n+1))
            ANS.append((1+N, i+n+1+N))
            ANS.append((i+n+1+N, i+n+N))
        ANS.append((a, a^c))
        ANS.append((c, (a^c)+N))
        ANS.append((1+N, b))
        ANS.append((a, b+N))
    # print(len(ANS))
    # print(ANS)
    if N == 3:
        ANS = [(1,2),(2,3),(3,4),(4,5),(5,6)]
    for ans in ANS:
        print(*ans)
    # print("len =", len(ANS))

Submission status: Accepted

Solution code:
n = int(input())

if bin(n).count('1') == 1:
    print('No')
else:
    print('Yes')
    print('1 2')
    print('2 3')
    print('3 {0}'.format(n + 1))
    print('{0} {1}'.format(n + 1, n + 2))
    print('{0} {1}'.format(n + 2, n + 3))

    if n >= 5:
        if n % 2 == 1:
            for i in range(4, n + 1):
                print('1 {0}'.format(i))
                if i % 2 == 0:
                    print('{0} {1}'.format(i, i + 1 + n))
                else:
                    print('{0} {1}'.format(i, i - 1 + n))
        else:
            for i in range(4, n):
                print('1 {0}'.format(i))
                if i % 2 == 0:
                    print('{0} {1}'.format(i, i + 1 + n))
                else:
                    print('{0} {1}'.format(i, i - 1 + n))
            print('{0} {1}'.format(n - 1, n))
            print('{0} {1}'.format((n - 1) ^ 1 ^ n, n * 2))

Submission status: Accepted

Solution code:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline
mii=lambda:map(int,input().split())

# n=4k+3 <=> the line graph works
# these fail: 1 2 4 8 16 32 ...

# 1 2 3 1 2 3
# 4 5 1 4 5
# 6 7 1 6 7

# so n=2k+1 (except n=1) works

def get(n):
    e=[]
    p=1
    while p*2<=n:
        p*=2
    if n!=p:
        # make line graph
        m=n
        while m%4!=3: m-=1
        for i in range(1,m):
            e.append([i,i+1])
            e.append([n+i,n+i+1])
        e.append([m,n+1])
        if n%4==1 or n%4==2:
            m=n
            if n%4==2: m-=1
            e.append([m-1,m])
            e.append([m,n+1])
            e.append([n+1,n+m-1])
            e.append([n+m-1,n+m])
        if n%4==0 or n%4==2:    # not a power of 2
            t=n-1
            e.append([n,t])
            for i in range(1,n+1):
                t^=i
                if t==n:
                    e.append([n+i,n+n])
                    break
    return e

n=int(input())
e=get(n)
if e:
    print("Yes")
    for i,j in e:
        print("%d %d"%(i,j))
else:
    print("No")

"""
def dfs(u):
    vis[u]=1
    root[u]^=(u-1)%n+1
    for v in g[u]:
        if vis[v]: continue
        root[v]=root[u]
        dfs(v)

for n in range(1,50):
    g=[[] for _ in range(2*n+1)]
    e=get(n)
    if not e: continue
    assert len(e)==n*2-1
    for i,j in e:
        g[i].append(j)
        g[j].append(i)
    for i in range(1,n+1):
        vis=[0]*(2*n+1)
        root=[0]*(2*n+1)
        dfs(i)
        assert root[n+i]==i
"""

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())
#a = [int(i) for i in readline().split()]
m = n
while m%2 ==0:
    m//=2
if m == 1:
    print("No")
    exit()
elif n%2:
    print("Yes")
    for i in range(2,n):
        print(i, i+1)
    print(n,1)
    print(1,n+n-1)
    for i in range(2,n,2):
        print(i+n,i+n+1)
    for i in range(2,n-2,2):
        print(i+n,i+n+3)
    print(n+1,n-1)
else:
    m=n-1
    print("Yes")
    for i in range(2,m):
        print(i, i+1)
    print(m,1)
    print(1,m+n-1)
    for i in range(2,m,2):
        print(i+n,i+n+1)
    for i in range(2,m-2,2):
        print(i+n,i+n+3)
    print(n+1,m-1)
    
    c = n^(n-2)^1
    print(c,n)
    if ((n-2)-c-1)%4==2:
        print(n-2,n+n)    
    else:
        print(n+1,n+n)

Submission status: Accepted

Solution code:
n = int(input())
b = 1
while b & n == 0:
    b *= 2
if b == n:
    print("No")
else:
    print("Yes")
    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:
        print(n, n + b)
        print(n - b + 1, n * 2)

Submission status: Accepted

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()
    p = [(1<<i) for i in range(100)]
    if n in p:
        print("No")
        quit()
    if n+1 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+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))
        for i in range(n):
            if p[i]&n:
                break
        ans.append((p[i+1]-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: Accepted

Solution code:
n=int(input())
l=1
while n>l:
    l*=2
if n==l:
    print("No")
    quit()
print("Yes")
for i in range((n-1)//2):
    t=i*2
    print(1,2+t)
    print(2+t,3+t)
    print(1,3+n+t)
    print(3+n+t,2+n+t)
print(3,1+n)
if n%2==0:
    print(n,(n&-n)+1+n)
    print(2*n,n-(n&-n))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())

# if power of 2
n = N.bit_length()
if N == 1 << (n-1):
    print('No')
    exit()

def solve(N):
    graph = []
    for n in range(2,N,2):
        graph.append((n,n+1))
        graph.append((n+1,1))
        graph.append((1,N+n))
        graph.append((N+n,N+n+1))
    graph.append((N+1,2))
    if N&1:
        return graph
    L = N.bit_length()
    n = 1 << (L-1)
    m = N ^ n ^ 1
    # n even, m odd
    graph.append((N,m))
    graph.append((n+N,N+N))
    return graph


graph = solve(N)

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

Submission status: Accepted

Solution code:
import sys, collections

def solve():
    input = sys.stdin.readline
    N = int(input())
    k = 1
    while k <= N:
        if k == N:
            print("No")
            break
        else: k *= 2
    else:
        if N % 2 == 1:
            print("Yes")
            ans = ""
            ans += "1 2\n"
            ans += "2 3\n"
            ans += "3 " + str(N + 1) + "\n"
            ans += str(N + 1) + " " + str(N + 2) + "\n"
            ans += str(N + 2) + " " + str(N + 3) + "\n"
            for i in range(2, N // 2 + 1):
                ans += str(2 * i) + " " + str(2 * i + 1) + "\n"
                ans += str(2*i+1) + " 1\n"
                ans += "1 " + str(N + 2*i) + "\n"
                ans += str(N+2*i) + " " + str(N+2*i+1) + "\n"
            print(ans)
        else:
            print("Yes")
            ans = ""
            ans += "1 2\n"
            ans += "2 3\n"
            ans += "3 " + str(N + 1) + "\n"
            ans += str(N + 1) + " " + str(N + 2) + "\n"
            ans += str(N + 2) + " " + str(N + 3) + "\n"
            for i in range(2, N // 2):
                ans += str(2 * i) + " " + str(2 * i + 1) + "\n"
                ans += str(2*i+1) + " 1\n"
                ans += "1 " + str(N + 2*i) + "\n"
                ans += str(N+2*i) + " " + str(N+2*i+1) + "\n"
            b = N ^ (N - 1)
            ans += str(N) + " " + str(N-1) + "\n"
            if b % 2 == 1:
                ans += str(N + b - 1) + " " + str(2 * N)
            else:
                ans += str(b + 1) + " " + str(2 * N)
            print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
n,k,i,v=int(input()),1,2,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: Runtime Error

Solution code:
n=int(input())
s=len(bin(n)-2)
if 2**(s-1)==n:
  print("No")
else:
  print("Yes")
  print(2**(s-1)-1,1+n)
  for i in range(1,2**(s-1)-2):
    print(i,i+1)
    print(i+n,i+n+1)
  print(2**(s-1),2**(s-1)+1)
  print(2**(s-1)+1,1)
  print(2**(s-1)+n,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: Runtime Error

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))  # 5
sen_end = 2 ** (dig_num - 1) - 1  # 15

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

for i in range(sen_end):
    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(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

    print(n, 2**one_goal)
    print(2*n, n - 2**one_goal)

Submission status: Runtime Error

Solution code:
n=int(input())
if n<3:
  print("No")
  exit()
if (n & (n-1))==0:
  print("No")
  exit()
ans=["1 2","2 3","3 "+str(1+n),str(1+n)+" "+str(2+n),str(2+n)+" "+str(3+n)]
if n%2!=0:
  for i in range(4,n):
    if i%2==0:
      ans.append(str(i)+" "+str(i+1))
      ans.append(str(i+1)+" "+str(1))
      ans.append(str(1)+" "+str(i+n))
      ans.append(str(i+n)+" "+str(i+n+1))
else:
  for i in range(4,n):
    if i%2==0:
      ans.append(str(i)+" "+str(i+1))
      ans.append(str(i+1)+" "+str(1))
      ans.append(str(1)+" "+str(i+n))
      ans.append(str(i+n)+" "+str(i+n+1))
  if n^3<n:
    ans.append(str(n)+" "+str(n^3))
    ans.append(str(n*2)+" "+str(2))
  else:
    ans.append(str(n)+" "+str(n-1))
    ans.append(str(n*2)+" "+str((n-1)^3+n)

print("Yes")
for i in range(len(ans)):
  print(ans[i])

Submission status: Runtime Error

Solution code:
n = int(input())

l = [False] * (n + 1)
p = [n]
b = bin(n)[2:][::-1]

pw = 0
for i in b:
    if i == '1':
        p.append(2 ** int(pw))
        l[2 ** pw] = True
    pw += 1

q = []
xr = 0
for i in range(1, n):
    if not l[i]:
        xr ^= i
        q.append(i)

# print(xr)
# print(p)
# print(q)

res1 = []
for i in p:
    res1.append(i)
for i in p:
    res1.append(i + n)
res2 = []
if xr == 0:
    res2 = [n]
    for i in q:
        res2.append(i)
    for i in q:
        res2.append(i + n)
else:
    res2 = []
    for i in q:
        res2.append(i)
    if xr not in p:
        print('!!!')
        exit(1)
    res2.append(xr)
    for i in q:
        res2.append(i + n)

res = []
for i,j in zip(res1, res1[1:]):
    res.append([i, j])
    if i == j:
        print('No')
        exit()
    # print(i, j)
for i,j in zip(res2, res2[1:]):
    res.append([i, j])
    if i == j:
        print('No')
        exit()
    # print(i, j)

if len(res) != 2 * n - 1:
    print('No')
else:
    print('Yes')
    for i in res:
        print(*i)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
check = [""]*m

if m%2==1:
    print(-1)
    exit()

for i in range(m):
    if check[i]=="ok":
        continue
    a = l[i][0]
    for j in range(i+1,m):
        if l[j][0]==a:
            check[j] = "ok"
            check[i] = "ok"
            break
        if l[j][1]==a:
            l[j] = [l[j][1], l[j][0]]
            check[j] = "ok"
            check[i] = "ok"
            break
    else:
        a = l[i][1]
        for j in range(i + 1, m):
            if l[j][0] == a:
                check[j] = "ok"
                l[i] = [l[i][1], l[i][0]]
                check[i] = "ok"
                break
            if l[j][1] == a:
                l[j] = [l[j][1], l[j][0]]
                check[j] = "ok"
                l[i] = [l[i][1], l[i][0]]
                check[i] = "ok"
                break
for k in l:
    print(str(k[0]) + " " + str(k[1]))

Submission status: Runtime Error

Solution code:
import math

N = int(input())
a = list(map(int, input().split(" ")))

def XOR(x):
	n = x.bit_length()
	count = 0
	while n > 0:
		count = count + x // int(math.pow(2,n-1))
		if x // int(math.pow(2,n-1)) == 1:
			x = x - int(math.pow(2,n-1))
		n = n - 1
	return count % 2

c_odd = 0
c_eve = 0
for i in range(N):
	if XOR(a[i])==1:
		c_odd = c_odd + 1
	else:
		c_eve = c_eve + 1

if N % 2 == 1:
	if c_odd == c_eve + 1 or c_odd == 0:
		print('Yes')
	else:
		print('No')
else:
	if c_odd == c_eve or c_odd == 0:
		print('Yes')
	else:
		print('No')

Submission status: Runtime Error

Solution code:
import math
import fractions

n = list(map(int, input().split()))

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