An undirected graph is called k-regular, if the degrees of all its vertices are equal k. An edge of a connected graph is called a bridge, if after removing it the graph is being split into two connected components.

Build a connected undirected k-regular graph containing at least one bridge, or else state that such graph doesn't exist.


-----Input-----

The single line of the input contains integer k (1 ≤ k ≤ 100) — the required degree of the vertices of the regular graph.


-----Output-----

Print "NO" (without quotes), if such graph doesn't exist. 

Otherwise, print "YES" in the first line and the description of any suitable graph in the next lines.

The description of the made graph must start with numbers n and m — the number of vertices and edges respectively. 

Each of the next m lines must contain two integers, a and b (1 ≤ a, b ≤ n, a ≠ b), that mean that there is an edge connecting the vertices a and b. A graph shouldn't contain multiple edges and edges that lead from a vertex to itself. A graph must be connected, the degrees of all vertices of the graph must be equal k. At least one edge of the graph must be a bridge. You can print the edges of the graph in any order. You can print the ends of each edge in any order.

The constructed graph must contain at most 10^6 vertices and 10^6 edges (it is guaranteed that if at least one graph that meets the requirements exists, then there also exists the graph with at most 10^6 vertices and at most 10^6 edges). 


-----Examples-----
Input
1

Output
YES
2 1
1 2



-----Note-----

In the sample from the statement there is a suitable graph consisting of two vertices, connected by a single edge.

Difficulty: HARD
Tags: Graph algorithms

Implementation

Constructive algorithms

Starter code:

Solutions:
def printWithSymmetry(u, v, offset):
	print('{0} {1}'.format(u, v))
	print('{0} {1}'.format(u + offset, v + offset))
k = int(input())
if k % 2 == 0:
	print('NO')
elif k == 1:
	print('YES')
	print('2 1')
	print('1 2')
else:
	print('YES')
	nodesNum = k + 2
	print('{0} {1}'.format(2 * nodesNum, nodesNum * k))
	print('1 {0}'.format(1 + nodesNum))
	printWithSymmetry(1, 2, nodesNum)
	for i in range(3, nodesNum):
		for j in range(i, nodesNum + 1):
			if i == j or (i > 5 and i % 2 == 0 and (j - i == 1)):
				continue
			printWithSymmetry(i, j, nodesNum)
	missingSec = k - 1
	for i in range(4, 4 + missingSec):
		printWithSymmetry(2, i, nodesNum)
	printWithSymmetry(1, 3, nodesNum)
	missingMain = k - 2 - 1
	if missingMain:
		for i in range(6, 6 + missingMain):
			printWithSymmetry(1, i, nodesNum)


def constructK2(v, k):
	res = set()
	for i in range(1, k):
		res.add((v[0], v[i]))
	for i in range(1, k):
		for j in range(1, k):
			if i != j:
				res.add((min(v[i], v[j]), max(v[i], v[j])))
	for i in range(2, k, 2):
		v1 = i
		v2 = i + 1
		if v2 >= k:
			v2 = 1
		res.remove((min(v[v1], v[v2]), max(v[v1], v[v2])))
	for i in range(1, k):
		res.add((v[i], v[k]))
		res.add((v[i], v[k + 1]))
	res.add((v[k], v[k + 1]))
	return res

def construct(k):
	res1 = constructK2([x for x in range(1, k + 3)], k)
	res2 = constructK2([x + k + 2 for x in range(1, k + 3)], k)
	return res1 | res2 | {(1, k + 3)}

def printRes(res):
	for ares in res:
		print(ares[0], ares[1])
k = int(input())
if k % 2 == 0:
	print('NO')
else:
	print('YES')
	if k == 1:
		print('2 1')
		print('1 2')
	else:
		print(2 * k + 4, ((2 * k + 4) * k - 2) // 2 + 1)
		res = construct(k)
		printRes(res)


k = int(input())
if k % 2 == 0:
	print('NO')
else:
	print('YES')
	if k == 1:
		print(2, 1)
		print(1, 2)
	else:
		n = 2 + (k - 1) * 4
		print(n, n * k // 2)
		print(1, 2 * k)
		for i in range(2, k + 1):
			for j in range(k + 1, 2 * k):
				print(i, j)
				print(i + 2 * k - 1, j + 2 * k - 1)
			print(1, i)
			print(2 * k, i + 2 * k - 1)
		for i in range(k + 1, 2 * k, 2):
			print(i, i + 1)
			print(i + 2 * k - 1, i + 2 * k)


k = int(input())
if k == 1:
	print('YES')
	print(2, 1)
	print(1, 2)
elif k % 2:
	print('YES')
	print(2 * k + 4, k * k + 2 * k)
	matrix = [[False] * (2 * k + 4) for _ in range(2 * k + 4)]
	for i in range(k + 1):
		for j in range(i + 1, k + 1):
			matrix[i][j] = True
	for i in range(k + 2, 2 * k + 3):
		for j in range(i + 1, 2 * k + 3):
			matrix[i][j] = True
	need = 0
	i = 0
	matrix[k + 1][-1] = True
	while need != k - 1:
		matrix[k + 1][2 * i] = True
		matrix[k + 1][2 * i + 1] = True
		matrix[-1][2 * i + k + 2] = True
		matrix[-1][2 * i + k + 3] = True
		matrix[2 * i][2 * i + 1] = False
		matrix[2 * i + k + 2][2 * i + k + 3] = False
		need += 2
		i += 1
	for i in range(2 * k + 4):
		for j in range(2 * k + 4):
			if matrix[i][j]:
				print(i + 1, j + 1)
else:
	print('NO')


k = int(input())
if k % 2 == 0:
	print('NO')
else:
	print('YES')
	reb = [[1, 2]]
	for v in range(3, k + 2):
		reb.append([1, v])
		reb.append([v, k + 2 * v - 4])
		reb.append([v, k + 2 * v - 3])
		reb.append([k + 2 * v - 4, k + 2 * v - 3])
		for u in range(v + 1, k + 2):
			if v + u != k + 4:
				reb.append([v, u])
			reb.append([k + 2 * v - 4, k + 2 * u - 4])
			reb.append([k + 2 * v - 3, k + 2 * u - 3])
	for v in range(3 * k, 4 * k - 1):
		reb.append([2, v])
		reb.append([v, 2 * v - 2 * k - 1])
		reb.append([v, 2 * v - 2 * k])
		reb.append([2 * v - 2 * k, 2 * v - 2 * k - 1])
		for u in range(v + 1, 4 * k - 1):
			if v + u != 7 * k - 2:
				reb.append([v, u])
			reb.append([2 * v - 2 * k, 2 * u - 2 * k])
			reb.append([2 * v - 2 * k - 1, 2 * u - 2 * k - 1])
	print(6 * k - 4, len(reb))
	for (a, b) in reb:
		print(a, b)


k = int(input())
if k & 1:
	print('YES')
	if k > 1:
		(a, b) = (k + 1, k + 2)
		t = [(a, b)]
		for i in [k, a, b]:
			t += [(i, j) for j in range(1, k)]
		for i in range(1, k):
			t += [(i, j) for j in range(i + 1 + (i & 1), k)]
		t = [(2 * b, b * k), (k, k + b)] + t + [(i + b, j + b) for (i, j) in t]
	else:
		t = [(2, 1), (1, 2)]
	for (i, j) in t:
		print(i, j)
else:
	print('NO')


l = [1]
l2 = []
n = int(input())

def f(a):
	for i in range(n - 1):
		l.append(i + a + 1)
		l2.append(a)
		for j in range(n - 1):
			l.append(j + a + 1 + n - 1)
			l2.append(i + a + 1)
	for i in range(n - 2):
		if i & 1 > 0:
			continue
		l.append(i + a + 1 + n - 1)
		l2.append(i + a + 1 + n)
if n & 1 > 0:
	print('YES')
	l2.append(2 * (n - 1) + 2)
	f(1)
	f(2 * (n - 1) + 2)
	print(str(4 * (n - 1) + 2) + ' ' + str(len(l)))
	for i in range(len(l)):
		print(str(l[i]) + ' ' + str(l2[i]))
else:
	print('NO')


import math, string, itertools, fractions, heapq, collections, re, array, bisect
from itertools import chain, dropwhile, permutations, combinations
from collections import defaultdict, deque

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

def main1(k):
	if k % 2 == 0:
		print('NO')
		return
	print('YES')
	n = 2 * (k ** 2 - k + 1)
	m = n * k // 2
	print(n, m)
	i = 0
	g = [[] for i in range(n + 1)]
	print(1, n // 2 + 1)
	off = 1
	for j in range(0, k - 1, 2):
		j1 = off + j + 1
		j2 = off + j + 2
		print(off, j1)
		print(off, j2)
		l1 = off + k + j * (k - 1)
		l2 = off + k + (j + 1) * (k - 1)
		for l in range(k - 1):
			print(j1, l1 + l)
			print(j2, l2 + l)
			for m in range(k - 1):
				print(l1 + l, l2 + m)
	off = n // 2 + 1
	for j in range(0, k - 1, 2):
		j1 = off + j + 1
		j2 = off + j + 2
		print(off, j1)
		print(off, j2)
		l1 = off + k + j * (k - 1)
		l2 = off + k + (j + 1) * (k - 1)
		for l in range(k - 1):
			print(j1, l1 + l)
			print(j2, l2 + l)
			for m in range(k - 1):
				print(l1 + l, l2 + m)

def main(k):
	if k % 2 == 0:
		print('NO')
		return
	print('YES')
	if k == 1:
		print('2 1')
		print('1 2')
		return
	n = 2 * k + 4
	m = n * k // 2
	e = []
	e.extend([(1, n // 2 + 1)])
	off = 1
	for j in range(off + 1, off + k):
		e.extend([(off, j)])
	for j in range(off + 1, off + k):
		for i in range(j + 1, off + k):
			if i == j + 1 and (j - off) % 2 == 1:
				continue
			e.extend([(j, i)])
		e.extend([(j, off + k), (j, off + k + 1)])
	e.extend([(off + k, off + k + 1)])
	off = n // 2 + 1
	for j in range(off + 1, off + k):
		e.extend([(off, j)])
	for j in range(off + 1, off + k):
		for i in range(j + 1, off + k):
			if i == j + 1 and (j - off) % 2 == 1:
				continue
			e.extend([(j, i)])
		e.extend([(j, off + k), (j, off + k + 1)])
	e.extend([(off + k, off + k + 1)])
	print(n, m)
	for x in e:
		print(*x)

def main_input(info=0):
	k = int(input())
	main(k)
main_input()


k = int(input())
if k % 2 == 0:
	print('NO')
elif k == 1:
	print('YES\n2 1\n1 2')
else:
	print('YES')
	print(2 * (k + 2), k * (k + 2))
	print(1, k + 3)
	for i in range(2):
		x = i * (k + 2)
		print(x + k + 1, x + k + 2)
		for j in range(k - 1):
			print(x + 1, x + j + 2)
			print(x + j + 2, x + k + 1)
			print(x + j + 2, x + k + 2)
		for a in range(1, (k - 3) // 2 + 1):
			for b in range(k - 1):
				print(x + 2 + b, x + 2 + (b + a) % (k - 1))


def solve():
	k = int(input())
	if k % 2 == 0:
		print('NO')
	elif k == 1:
		print('YES')
		print('2 1')
		print('1 2')
	else:
		print('YES')
		global nodesNum
		nodesNum = k + 2
		print('{0} {1}'.format(2 * nodesNum, nodesNum * k))
		print('1 {0}'.format(1 + nodesNum))
		for i in range(2, nodesNum):
			for j in range(i, nodesNum + 1):
				if i == j or (i > 3 and j - i == 1 and (i % 2 == 0)):
					continue
				printWithSymmetry(i, j)
		for i in range(4, 4 + k - 1):
			printWithSymmetry(1, i)

def printWithSymmetry(u, v):
	print('{0} {1}\n{2} {3}'.format(u, v, u + nodesNum, v + nodesNum))
solve()


def ic(c, n):
	return (k + 1) * c + n

def func():
	if k % 2 == 0:
		return print('NO')
	if k == 1:
		return print('YES\n2 1\n1 2')
	edges = set()
	b1 = 4 * (k + 1) + 1
	b2 = b1 + 1
	for c in range(4):
		for i in range(ic(c, 1), ic(c, k + 1) + 1):
			for j in range(i + 1, ic(c, k + 1) + 1):
				edges.add((i, j))
	for i in range(1, (k - 1) // 2 + 1):
		edges.remove((ic(0, i), ic(0, i + 1)))
		edges.remove((ic(1, i), ic(1, i + 1)))
		edges.remove((ic(2, i), ic(2, i + 1)))
		edges.remove((ic(3, i), ic(3, i + 1)))
		edges.add((ic(0, i), b1))
		edges.add((ic(1, i), b1))
		edges.add((ic(2, i), b2))
		edges.add((ic(3, i), b2))
		edges.add((ic(0, i + 1), ic(1, i + 1)))
		edges.add((ic(2, i + 1), ic(3, i + 1)))
	edges.add((b1, b2))
	print('YES')
	print(b2, len(edges))
	for edge in edges:
		print(edge[0], edge[1])
k = int(input())
func()


def main():
	k = int(input())
	if k & 1:
		print('YES')
		n = 2 * (2 * k - 1)
		m = k * (2 * k - 1)
		print(n, m)
		n >>= 1
		print(1, 1 + n)
		for i in range(2, k + 1):
			print(1, i)
			print(1 + n, i + n)
			for j in range(k + 1, 2 * k):
				print(i, j)
				print(i + n, j + n)
		for i in range(k + 1, 2 * k, 2):
			print(i, i + 1)
			print(i + n, i + 1 + n)
	else:
		print('NO')
	return 0
main()


k = int(input())
if k == 1:
	print('YES\n2 1\n1 2')
elif k % 2 == 0:
	print('NO')
else:
	print('YES')
	n = k + 1
	z = (k - 1) // 2
	print(2 * k + 4, n * (n - 1) + 1 + 2 * z)
	l1 = list(range(1, 2 * z + 1, 2)) + [-1]
	l2 = list(range(k + 4, k + 2 * z + 4, 2)) + [-1]
	z = 0
	for i in range(1, n):
		for j in range(i + 1, n + 1):
			if i == l1[z]:
				print(i, k + 2)
				print(i + 1, k + 2)
				z += 1
			else:
				print(i, j)
	print(k + 2, k + 3)
	z = 0
	n = 2 * k + 4
	for i in range(k + 4, n):
		for j in range(i + 1, n + 1):
			if i == l2[z]:
				print(i, k + 3)
				print(i + 1, k + 3)
				z += 1
			else:
				print(i, j)


k = int(input())
n = 0

def build_half(offset):
	for i in range(1, k):
		print(offset + (n >> 1), offset + i)
		for j in range(k - 1):
			print(offset + i, offset + k + j)
	for i in range(1, k, 2):
		print(offset + k + i - 1, offset + k + i)
if k & 1:
	print('YES')
	n = 1 + (k - 1 << 1) << 1
	print(n, n * k >> 1)
	build_half(0)
	build_half(n >> 1)
	print(n >> 1, n)
	print()
else:
	print('NO')


k = int(input())
if k % 2 == 0:
	print('NO')
	exit(0)
print('YES')
vs = 4 * k - 2
es = int(vs * k / 2)
print(vs, es)
print(1, 2 * k)
for g in range(2):
	shift = g * (2 * k - 1)
	for i in range(2, k + 1):
		print(1 + shift, i + shift)
	for i in range(2, k + 1):
		for j in range(k + 1, 2 * k):
			print(i + shift, j + shift)
	for i in range(k + 1, 2 * k, 2):
		print(i + shift, i + 1 + shift)


x = int(input())
if x % 2 == 0:
	print('NO')
	quit()
	print('WHY IS CF SO HARD Dx')
if x == 1:
	print('YES')
	print(2, 1)
	print(1, 2)
else:
	print('YES')
	sides = 2 * x + 4
	half = x + 2
	e = sides * x // 2
	print(sides, e)
	print(x + 2, x + 3)
	dead = [[1, x + 2], [2, x + 2]]
	for i in range(3, x + 2, 2):
		dead.append([i, i + 1])
	for i in range(1, x + 3):
		for j in range(i + 1, x + 3):
			if [i, j] not in dead and [j, i] not in dead:
				print(i, j)
				print(sides - i + 1, sides - j + 1)


def nextEdge():
	global v
	for i in range(1, v + 1):
		for j in range(i + 1, v + 1):
			yield (i, j)
k = int(input())
if k % 2 == 0:
	print('NO')
elif k == 1:
	print('YES', '2 1', '1 2', sep='\n')
else:
	n = 2 * k + 4
	m = k * (k + 2)
	print('YES')
	print(n, m, sep=' ')
	a = [i for i in range(1, k)] + [i for i in range(k + 4, 2 * k + 3)]
	b = [k + 2] * (k - 1) + [k + 3] * (k - 1)
	a += [k + 2]
	b += [k + 3]
	v = k + 1
	curr = (1, 2)
	count = k - 1
	for i in nextEdge():
		if count == 0 or (i != curr and count > 0):
			a.append(i[0])
			b.append(i[1])
			a.append(i[0] + k + 3)
			b.append(i[1] + k + 3)
		else:
			curr = (curr[1] + 1, curr[1] + 2)
			count -= 2
	for i in range(m):
		print(a[i], b[i], sep=' ')


def generate(cur, n):
	comp = []
	edge = []
	cur += 1
	comp.append([cur])
	layer1 = []
	for _ in range(n - 1):
		cur += 1
		layer1.append(cur)
	comp.append(layer1)
	layer2 = []
	for _ in range(n - 1):
		cur += 1
		layer2.append(cur)
	comp.append(layer2)
	for (layer1, layer2) in zip(comp[:-1], comp[1:]):
		for x in layer1:
			for y in layer2:
				edge.append([x, y])
	for i in range(0, len(comp[-1]), 2):
		edge.append([comp[-1][i], comp[-1][i + 1]])
	return (cur, edge)

def solve():
	n = int(input())
	if n % 2 == 0:
		print('NO')
		return
	cur = 0
	(cur1, edge1) = generate(cur, n)
	(cur2, edge2) = generate(cur1, n)
	print('YES')
	print(cur2, len(edge1) + len(edge2) + 1)
	s = ''
	for (u, v) in edge1:
		s += str(u) + ' ' + str(v)
		s += '\n'
	for (u, v) in edge2:
		s += str(u) + ' ' + str(v)
		s += '\n'
	s += str(1) + ' ' + str(1 + cur1)
	print(s)
solve()


import sys

def main():
	inp = [int(x) for x in sys.stdin.read().split()]
	ii = 0
	k = inp[ii]
	if k % 2 == 0:
		print('NO')
		sys.exit()
	s = 2 * k - 1
	n = 2 * s
	m = s * k
	print('YES')
	print(n, m)
	print(1, 1 + s)
	for x in range(k - 1):
		print(1, x + 2)
		print(1 + s, x + 2 + s)
	for x in range(k - 1):
		for y in range(k - 1, 2 * k - 2):
			print(x + 2, y + 2)
			print(x + 2 + s, y + 2 + s)
	for y in range(k + 1, 2 * k, 2):
		print(y, y + 1)
		print(y + s, y + 1 + s)
main()


k = int(input())
if k == 1:
	print('YES\n2 1\n1 2')
elif k & 1:
	n = k + 2
	t = [(k + 1, n)]
	for i in range(1, k):
		t += [(i, j) for j in range(i + 1 + (i & 1), k + 3)]
	t = [(2 * n, n * k), (k, k + n)] + t + [(i + n, j + n) for (i, j) in t]
	print('YES')
	for (i, j) in t:
		print(i, j)
else:
	print('NO')


import sys
input = []
input_index = 0

def next(type, number=None):

	def next():
		global input, input_index
		while input_index == len(input):
			if sys.stdin:
				input = sys.stdin.readline().split()
				input_index = 0
			else:
				raise Exception()
		input_index += 1
		return input[input_index - 1]
	if number is None:
		result = type(next())
	else:
		result = [type(next()) for _ in range(number)]
	return result
k = next(int)
vn = 0
es = []
if k % 2 == 1:

	def get_full(i, w):
		global vn
		vn += w
		for j in range(i, i + w):
			for jj in range(j + 1, i + w):
				es.append((j, jj))

	def get_c(i):
		global vn
		vn += k - 1
		q = i + k - 1
		for j in range(i, i + k - 1, 2):
			es.append((j, i - 1))
			es.append((j + 1, i - 1))
			get_full(q, k - 1)
			for jj in range(q, q + k - 1):
				es.append((j, jj))
				es.append((j + 1, jj))
			q += k - 1
		return q
	j = get_c(1)
	es.append((0, j))
	get_c(j + 1)
	vn += 2
	print('YES')
	print('%s %s' % (vn, len(es)))
	for (a, b) in es:
		print('%s %s' % (a + 1, b + 1))
else:
	print('NO')


import sys
input = sys.stdin.readline

def solve():
	k = int(input())
	if k % 2 == 0:
		print('NO')
		return
	print('YES')
	if k == 1:
		print('2 1')
		print('1 2')
		return
	n = k + 1
	v = 2 * (n + 1)
	e = n * n - 1
	print(v, e)
	g = [[0 for _ in range(v)] for _ in range(v)]
	for i in range(n - 1):
		g[i][i + 1] = 1
	g[0][n - 1] = 1
	for i in range(1, n):
		g[i][n] = 1
	diag = n - 4
	for i in range(n - 2):
		for j in range(i + 2, i + 2 + diag // 2):
			if j < n:
				g[i][j] = 1
		for j in range(i + 3 + diag // 2, i + 3 + diag):
			if j < n:
				g[i][j] = 1
	for i in range(n + 1, n + 1 + n - 1):
		g[i][i + 1] = 1
	g[n + 1][n + 1 + n - 1] = 1
	for i in range(n + 1 + 1, n + 1 + n):
		g[i][n + 1 + n] = 1
	diag = n - 4
	for i in range(n + 1, n + 1 + n - 2):
		for j in range(i + 2, i + 2 + diag // 2):
			if j < n + 1 + n:
				g[i][j] = 1
		for j in range(i + 3 + diag // 2, i + 3 + diag):
			if j < n + 1 + n:
				g[i][j] = 1
	g[0][n + 1] = 1
	for i in range(len(g)):
		for j in range(len(g[0])):
			if g[i][j] == 1:
				print(i + 1, j + 1)
solve()


k = int(input())
if k % 2 == 0:
	print('NO')
	exit(0)
print('YES')
v = 4 * k - 2
print(v, k * v // 2)
for i in range(k):
	if i % 2 == 1:
		print(i, i + 1)
for i in range(1, k):
	for j in range(k, 2 * k - 1):
		print(i, j)
for i in range(k, 2 * k - 1):
	print(i, 2 * k - 1)
print(2 * k - 1, 2 * k)
for i in range(2 * k + 1, 3 * k):
	print(2 * k, i)
for i in range(2 * k + 1, 3 * k):
	for j in range(3 * k, 4 * k - 1):
		print(i, j)
for i in range(3 * k, 4 * k - 1):
	if (i - 3 * k) % 2 == 0:
		print(i, i + 1)


k = int(input())
if k % 2 == 0:
	print('NO')
	exit(0)
print('YES')
if k == 1:
	print(2, 1)
	print(1, 2)
	exit(0)
size = 2 * (k + 2)
print(size, size * k // 2)
res_table = []
for i in range(1, k + 3):
	for j in range(1, i):
		if i + j != k + 4 and (i != k + 2 or j != 1):
			print(i, j)
			print(size - j + 1, size - i + 1)
print(size // 2, size // 2 + 1)


def f(k):
	if k == 1:
		print('YES')
		print('2 1\n1 2')
		return
	if k % 2 == 0:
		print('NO')
		return
	print('YES')
	ver = 2 + (k - 1) * 4
	print(ver, ver * k // 2)
	print(1, 2 * k)
	for i in range(2, k + 1):
		for j in range(k + 1, 2 * k):
			print(i, j)
			print(i + 2 * k - 1, j + 2 * k - 1)
		print(1, i)
		print(2 * k, i + 2 * k - 1)
	for i in range(k + 1, 2 * k, 2):
		print(i, i + 1)
		print(i + 2 * k - 1, i + 2 * k)
k = int(input())
f(k)