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<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//2-1))
    ans.append(str(n*2)+" "+str((n//2-1)^n-1+n))
print("Yes")
for i in range(len(ans)):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


def main():
    n = get_int()
    m = n.bit_length()
    if 2 ** (m - 1) == n:
        print('No')
        return
    print('Yes')
    if n % 2 == 1:
        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(1, i)
            print(i, i + 1)
            print(1, n + i + 1)
            print(n + i + 1, n + i)
        return
    for i in range(1, 2 ** (m - 1) - 1):
        print(i, i + 1)
        print(n + i, n + i + 1)
    print(2 ** (m - 1) - 1, n + 1)
    x, y = 2, 3
    for i in range(2 ** (m - 1), n, 2):
        print(x, i)
        print(i, i + 1)
        print(y, n + i + 1)
        print(n + i + 1, n + i)
    print(x, n)
    print(n - 2, 2 * n)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Submission status: Wrong Answer

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 = 0
        while N >> k > 0:
            k += 1
        a = 1 << (k-1)
        if N - a - 1 == 1:
            print((a^1)+N, N)
            print(N^a, 2*N)
        else:
            print(a, N)
            print(N - (1 << (k-1)) - 1, 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: Wrong Answer

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 + 3, 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: Wrong Answer

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//2-1))
    ans.append(str(n*2)+" "+str((n//2-1)^3+n))
print("Yes")
for i in range(len(ans)):
  print(ans[i])

Submission status: Wrong Answer

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
        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 + 3, 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: Wrong Answer

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: Wrong Answer

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
    if m < 3:
        if bin(l).count('1') == 1:
            print('No')
            return
    ans = ['{} {}'.format(x, y) for x, y in ((1, 2), (2, 3), (3, 1 + n), (1 + n, 2 + n), (2 + n, 3 + n))]
    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: Wrong Answer

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
    if m < 3:
        if bin(l).count('1') == 1:
            print('No')
            return
    ans = ['{} {}'.format(x, y) for x, y in ((1, 2), (2, 3), (3, 1 + n), (1 + n, 2 + n), (2 + n, 3 + n))]
    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 + 3, i + n + 1), (i + n + 1, i + n + 2), (i + n + 2, i + n + 3)))

    if n == 3:
        print('Yes')
        print('\n'.join(ans))
        return
    elif 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: Wrong Answer

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))
  ans.append(str(n)+" "+str(n^3))
  ans.append(str(n*2)+" "+str(2))
print("Yes")
for i in range(len(ans)):
  print(ans[i])

Submission status: Wrong Answer

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+n))
      ans.append(str(1+n)+" "+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))
  ans.append(str(n)+" "+str(n^3+n))
  ans.append(str(n*2)+" "+str(2))
print("Yes")
for i in range(len(ans)):
  print(ans[i])

Submission status: Wrong Answer

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+n))
      ans.append(str(1+n)+" "+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+n))
      ans.append(str(1+n)+" "+str(i+n))
      ans.append(str(i+n)+" "+str(i+n+1))
  ans.append(str(n)+" "+str(n^3+n))
  ans.append(str(n*2)+" "+str(2))
print("Yes")
for i in range(len(ans)):
  print(ans[i])

Submission status: Wrong Answer

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+n))
      ans.append(str(1+n)+" "+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+n))
      ans.append(str(1+n)+" "+str(i+n))
      ans.append(str(i+n)+" "+str(i+n+1))
  ans.append(str(n)+" "+str(n^3))
  ans.append(str(n*2)+" "+str(2))
print("Yes")
for i in range(len(ans)):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
def solve(n):
    if n < 3:
        print('No')
        return
    d, m = divmod(n, 4)
    l = d * 4
    if m < 3:
        if bin(l).count('1') == 1:
            print('No')
            return
    ans = ['{} {}'.format(x, y) for x, y in ((1, 2), (2, 3), (3, 1 + n), (1 + n, 2 + n), (2 + n, 3 + n))]
    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 + 3, i + n + 1), (i + n + 1, i + n + 2), (i + n + 2, i + n + 3)))

    if d == 0:
        print('Yes')
        print('\n'.join(ans))
        return
    elif 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: Wrong Answer

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+1):
    if i%2==0:
      ans.append(str(i)+" "+str(i+1))
      ans.append(str(i+1)+" "+str(1+n))
      ans.append(str(1+n)+" "+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+n))
      ans.append(str(1+n)+" "+str(i+n))
      ans.append(str(i+n)+" "+str(i+n+1))
  ans.append(str(n)+" "+str(n^2))
  ans.append(str(n*2)+" "+str(2))
print("Yes")
for i in range(len(ans)):
  print(ans[i])

Submission status: Wrong Answer

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(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)
    if n2==3:
      print(2,2*n)
    else:
      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: Wrong Answer

Solution code:
def solve(n):
    if n < 3:
        print('No')
        return
    d, m = divmod(n, 4)
    l = d * 4
    if m < 3:
        if bin(l).count('1') == 1:
            print('No')
            return
    ans = ['{} {}'.format(x, y) for x, y in ((1, 2), (2, 3), (3, 1 + n), (1 + n, 2 + n), (2 + n, 3 + n))]
    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 + 3, i + n + 1), (i + n + 1, i + n + 2), (i + n + 2, i + n + 3)))

    if d == 0:
        print('Yes')
        print('\n'.join(ans))
        return
    elif 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, 2))
        ans.append('{} {}'.format(l + 2 + n, prev + 1))

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

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


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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


def main():
    n = get_int()
    m = n.bit_length()
    if 2 ** (m - 1) == n:
        print('No')
        return
    print('Yes')
    if m == 2:
        # no node between 1 and N + 1
        for i in range(1, 6):
            print(i, i + 1)
        return
    for i in range(1, 2 ** (m - 1) - 1):
        print(i, i + 1)
        print(n + i, n + i + 1)
    print(2 ** (m - 1) - 1, n + 1)
    x, y = 1, 1
    if n % 2 == 0:
        x, y = 2, 3
    for i in range(2 ** (m - 1), n, 2):
        print(x, i)
        print(i, i + 1)
        print(y, n + i + 1)
        print(n + i + 1, n + i)
    if n % 2 == 0:
        print(x, n)
        print(n - 2, 2 * n)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Submission status: Wrong Answer

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(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: Wrong Answer

Solution code:
def solve(n):
    if n < 3:
        print('No')
        return
    d, m = divmod(n, 4)
    l = d * 4
    if m < 3:
        if bin(d * 4).count('1') == 1:
            print('No')
            return
    ans = ['{} {}'.format(x, y) for x, y in ((1, 2), (2, 3), (3, 1 + n), (1 + n, 2 + n), (2 + n, 3 + n))]
    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 + 3, i + n + 1), (i + n + 1, i + n + 2), (i + n + 2, i + n + 3)))

    if d == 0:
        print('Yes')
        print('\n'.join(ans))
        return
    elif 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, 2 + n))
        ans.append('{} {}'.format(l + 2 + n, prev))

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


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

Submission status: Wrong Answer

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)
        print(N+3, i+1+N)

Submission status: Wrong Answer

Solution code:
def solve(n):
    d, m = divmod(n, 4)
    l = d * 4
    if m < 3:
        if bin(d * 4).count('1') == 1:
            print('No')
            return
    ans = ['{} {}'.format(x, y) for x, y in ((1, 2), (2, 3), (3, 1 + n), (1 + n, 2 + n), (2 + n, 3 + n))]
    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 + 3, i + n + 1), (i + n + 1, i + n + 2), (i + n + 2, i + n + 3)))

    if d == 0:
        print('Yes')
        print('\n'.join(ans))
        return
    elif 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, 2 + n))
        ans.append('{} {}'.format(l + 2 + n, prev))

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


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

Submission status: Wrong Answer

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)
        i += 2
    else:
        print(i-1, i+1)
        print(N+3, i+1+N)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n<3:
  print("No")
  exit()
if n%2==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)]
for i in range(4,n+1):
  if i%2==0:
    ans.append(str(i)+" "+str(i+1))
    ans.append(str(i+1)+" "+str(1+n))
    ans.append(str(1+n)+" "+str(i+n))
    ans.append(str(i+n)+" "+str(i+n+1))
print("Yes")
for i in range(len(ans)):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


def main():
    n = get_int()
    m = n.bit_length()
    if 2 ** (m - 1) == n:
        print('No')
        return
    print('Yes')
    if m == 2:
        # no node between 1 and N + 1
        for i in range(1, 6):
            print(i, i + 1)
        return
    for i in range(1, 2 ** (m - 1) - 1):
        print(i, i + 1)
        print(n + i, n + i + 1)
    print(2 ** (m - 1) - 1, n + 1)
    x, y = 1, 1
    if n % 2 == 0:
        x, y = 2, 3
    for i in range(2 ** (m - 1), n, 2):
        print(x, i)
        print(i, i + 1)
        print(y, n + i + 1)
        print(n + i + 1, n + i)
    if n % 2 == 0:
        print(x, n)
        print(2 ** (m - 1), 2 * n)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Submission status: Wrong Answer

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-1, 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)
if i+2 < N:
    print(i-1, i+1)
    print(N+3, i+1+N)

Submission status: Wrong Answer

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