Read problems statements in mandarin chinese, russian and vietnamese as well. 

Chef Ada loves trees, she thinks that the beauty of a tree is determined by the distance between its center and centroid. If the tree has multiple centers or centroids, then the beauty is the maximum among every possible pair.

As a reward for her delicious dishes (and awesome coding skills), CodeChef is going to give a present to Chef Ada, and of course it must be a tree! But not any tree, we want to give her one with n nodes, and beauty b. Help find such a tree.

------ Input ------ 

The first line of input contains one number T, the number of test cases.

Each test case contains two integers n and b, the desired number of vertices and beauty.

------ Output ------ 

For each test case, if no tree satisfies the conditions print "NO" in a new line.

Otherwise, print "YES" in a new line and describe any valid tree. Print n-1 more lines, each with two integers u_{i}, v_{i} (1 ≤ u_{i}, v_{i} ≤ n) denoting the indices of the vertices connected by an edge in the tree.

------ Constraints ------ 

1 ≤ T ≤ 10^{4}
2 ≤ n ≤ 100
0 ≤ b ≤ n-1

------ Notes ------ 

A vertex u is a centroid if after removing u from the tree, the size of any of the resulting connected components is at most n/2.

Lef f(x) be the greatest distance from u to any other vertex of the tree. A vertex u is a center if f(u) ≤ f(v)  for any other vertex v.

----- Sample Input 1 ------ 
1
4 0
----- Sample Output 1 ------ 
YES
1 2
1 3
1 4
----- explanation 1 ------ 

Vertex 1 is the center and centroid of the tree.

Difficulty: VERY_HARD
Tags: Graph algorithms

Constructive algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, b) = map(int, input().split())
	if n == 2:
		if b == 1:
			print('YES')
			print('1 2')
		else:
			print('NO')
		continue
	if n < 4 * b:
		print('NO')
		continue
	print('YES')
	l = []
	for j in range(2 * b):
		l.append([j + 1, j + 2])
	for k in range(2 * b + 1, n):
		l.append([1, k + 1])
	for z in l:
		print(*z)


for _ in range(int(input())):
	(n, b) = map(int, input().split())
	if n == 2:
		if b == 1:
			print('YES')
			print('1 2')
		else:
			print('NO')
		continue
	if n < 4 * b:
		print('NO')
		continue
	print('YES')
	sol = []
	for i in range(2 * b):
		sol.append([i + 1, i + 2])
	for i in range(2 * b + 1, n):
		sol.append([1, i + 1])
	for i in sol:
		print(*i)


import io
import sys

def test_data():
	return io.StringIO('3\n4 0\n2 0\n2 1')

def get_input(source):
	with source as lines:
		t = int(next(lines))
		for _ in range(t):
			(n, b) = map(int, next(lines).split(' '))
			yield (n, b)

def calc(n, b):
	if n == 2 and b == 1:
		return [(1, 2)]
	if n < 3 or (b != 0 and n / b < 4):
		return None
	edges = []
	broom_length = b * 2 + 1
	for i in range(1, n):
		i += 1
		edges.append((i, i + 1 if i < broom_length else 1))
	return edges
inp = test_data() if '-test' in sys.argv else sys.stdin
for args in get_input(inp):
	edges = calc(*args)
	if edges == None:
		print('NO')
	else:
		print('YES')
		for e in edges:
			print('{} {}'.format(*e))


t = int(input())
for test in range(t):
	(n, b) = map(int, input().split())
	if n == 2:
		if b == 1:
			print('YES')
			print(1, 2)
		else:
			print('NO')
	elif n < 4 * b:
		print('NO')
	else:
		print('YES')
		for i in range(1, 2 * b + 1):
			print(i, i + 1)
		start = 2 * b + 2
		while start <= n:
			print(1, start)
			start += 1


for t in range(int(input())):
	(n, b) = map(int, input().split())
	if b == 0:
		if n == 2:
			print('NO')
			continue
		print('YES')
		for i in range(2, n + 1):
			print(1, i)
		continue
	for g in range(1, n):
		c = n - g
		ctra = [c // 2 + 1]
		if (c + 1) % 2 == 0:
			ctra.append(ctra[-1] + 1)
		l = c - 1
		r = g
		ctd = c
		ctda = []
		while l >= 0:
			if l <= n // 2 and r <= n // 2:
				ctda.append(ctd)
			ctd -= 1
			l -= 1
			r += 1
		m = None
		for x in ctra:
			for y in ctda:
				if abs(x - y) == b:
					m = (g, x, y)
					break
		if m is not None:
			break
	if m:
		print('YES')
		for i in range(2, n - m[0] + 1):
			print(i - 1, i)
		for i in range(n - m[0] + 1, n + 1):
			print(n - m[0], i)
	else:
		print('NO')