Mathematical Circus (Codeforces 1719B)
Tags: Math, constructive algorithms

A new entertainment has appeared in Buryatia — a mathematical circus! The magician shows two numbers to the audience — $$$n$$$ and $$$k$$$, where $$$n$$$ is even. Next, he takes all the integers from $$$1$$$ to $$$n$$$, and splits them all into pairs $$$(a, b)$$$ (each integer must be in exactly one pair) so that for each pair the integer $$$(a + k) \cdot b$$$ is divisible by $$$4$$$ (note that the order of the numbers in the pair matters), or reports that, unfortunately for viewers, such a split is impossible.Burenka really likes such performances, so she asked her friend Tonya to be a magician, and also gave him the numbers $$$n$$$ and $$$k$$$.Tonya is a wolf, and as you know, wolves do not perform in the circus, even in a mathematical one. Therefore, he asks you to help him. Let him know if a suitable splitting into pairs is possible, and if possible, then tell it.

Input: The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The following is a description of the input data sets.The single line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 10^9$$$, $$$n$$$ is even) — the number of integers and the number being added $$$k$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, first output the string "YES" if there is a split into pairs, and "NO" if there is none.If there is a split, then in the following $$$\frac{n}{2}$$$ lines output pairs of the split, in each line print $$$2$$$ numbers — first the integer $$$a$$$, then the integer $$$b$$$.

Note: In the first test case, splitting into pairs $$$(1, 2)$$$ and $$$(3, 4)$$$ is suitable, same as splitting into $$$(1, 4)$$$ and $$$(3, 2)$$$.In the second test case, $$$(1 + 0) \cdot 2 = 1 \cdot (2 + 0) = 2$$$ is not divisible by $$$4$$$, so there is no partition.

Sample Inputs:
4
4 1
2 0
12 10
14 11

Sample Outputs:
YES
1 2
3 4
NO
YES
3 4
7 8
11 12
2 1
6 5
10 9
YES
1 2
3 4
5 6
7 8
9 10
11 12
13 14

Solution (Python):
""""""

def i():
    (n, k) = map(int, input().split())
    if k % 2:
        c = [f'{x - 1} {x}\n' for x in range(2, n + 1, 2)]
    elif k % 4:
        c = [f'{x} {x - 1}\n' for x in range(2, n + 1, 4)]
        c += [f'{x - 1} {x}\n' for x in range(4, n + 1, 4)]
    else:
        return 'NO\n'
    return 'YES\n' + ''.join(c)
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print(''.join(a), end='')

Solution (Python):
t = int(input())
ans = []
for e in range(t):
    (n, k) = map(int, input().split())
    if k % 4 == 0:
        ans.append('NO')
    elif k % 4 in [1, 3]:
        ans.append('YES')
        for e in range(1, n + 1, 2):
            ans.append(f'{e} {e + 1}')
    else:
        ans.append('YES')
        for e in range(1, n + 1, 2):
            if (e + 1) % 4 == 0:
                ans.append(f'{e} {e + 1}')
            else:
                ans.append(f'{e + 1} {e}')
print('\n'.join(ans))

Solution (Python):
import sys
INF = 10 ** 20
MOD = 10 ** 9 + 7
from math import gcd
from math import ceil, log2, factorial
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

def fastio():
    import sys
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
I = lambda : list(map(int, input().split()))
TESTS = 1
''

def solve():
    (n, k) = I()
    if k == 0:
        print('NO')
        return
    aight = k % 2
    if aight:
        print('YES')
        for i in range(1, n + 1, 2):
            print(i, i + 1)
    else:
        aight = k % 4
        if not aight:
            print('NO')
        else:
            print('YES')
            for i in range(0, n, 4):
                print(i + 2, i + 1)
                if i + 3 <= n:
                    print(i + 3, i + 4)

def main():
    if not TESTS:
        solve()
        return
    (t,) = I()
    while t:
        solve()
        t -= 1
if __name__ == '__main__':
    main()