Let's call an undirected graph of n vertices p-interesting, if the following conditions fulfill:   the graph contains exactly 2n + p edges;  the graph doesn't contain self-loops and multiple edges;  for any integer k (1 ≤ k ≤ n), any subgraph consisting of k vertices contains at most 2k + p edges. 

A subgraph of a graph is some set of the graph vertices and some set of the graph edges. At that, the set of edges must meet the condition: both ends of each edge from the set must belong to the chosen set of vertices. 

Your task is to find a p-interesting graph consisting of n vertices.


-----Input-----

The first line contains a single integer t (1 ≤ t ≤ 5) — the number of tests in the input. Next t lines each contains two space-separated integers: n, p (5 ≤ n ≤ 24; p ≥ 0; $2 n + p \leq \frac{n(n - 1)}{2}$) — the number of vertices in the graph and the interest value for the appropriate test. 

It is guaranteed that the required graph exists.


-----Output-----

For each of the t tests print 2n + p lines containing the description of the edges of a p-interesting graph: the i-th line must contain two space-separated integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}) — two vertices, connected by an edge in the resulting graph. Consider the graph vertices numbered with integers from 1 to n. 

Print the answers to the tests in the order the tests occur in the input. If there are multiple solutions, you can print any of them.


-----Examples-----
Input
1
6 0

Output
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6

Source: codeforces | Difficulty: MEDIUM
Tags: Complete search

Graph algorithms

Constructive algorithms


Solutions:
t = int(input())
while t > 0:
	[n, p] = map(int, input().split(' '))
	count = int(0)
	for i in range(n):
		j = i + 2
		while j <= n:
			count = count + 1
			print(str(i + 1) + ' ' + str(j))
			if count == 2 * n + p:
				break
			j = j + 1
		if j <= n:
			break
	t = t - 1


def solve(n, p):
	cnt = 2 * n + p
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			print(i, j)
			cnt -= 1
			if cnt == 0:
				return

def main():
	t = int(input())
	for _ in range(t):
		(n, p) = map(int, input().split())
		solve(n, p)

def __starting_point():
	main()
__starting_point()


from sys import stdin, setrecursionlimit
t = int(stdin.readline().strip())
for _ in range(t):
	(n, p) = list(map(int, stdin.readline().split()))
	count = 0
	flag = 0
	for i in range(1, n + 1):
		if flag == 1:
			break
		for j in range(i + 1, n + 1):
			if count == 2 * n + p:
				flag = 1
				break
			print(i, j)
			count += 1


for t in range(int(input())):
	(n, p) = map(int, input().split())
	for v in range(2 * n + p):
		print(v % n + 1, (v % n + 1 + v // n) % n + 1)


from sys import stdin

def main():
	t = int(stdin.readline())
	for _ in range(t):
		(n, p) = map(int, stdin.readline().split())
		for i in range(n):
			print(i + 1, (i + 1) % n + 1)
		count = n + p
		ok = False
		for i in range(n):
			for j in range(i + 1, n):
				if (i - 1) % n != j and (i + 1) % n != j:
					print(i + 1, j + 1)
					count -= 1
					if count == 0:
						ok = True
						break
			if ok:
				break
main()


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(ele, end='\n')
for _ in range(L()[0]):
	(n, p) = L()
	A = []
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			A.append([i, j])
	for i in range(2 * n + p):
		print(*A[i])
endtime = time.time()


t = int(input())
for _ in range(t):
	(n, p) = [int(x) for x in input().split()]
	p += 2 * n
	for i in range(1, n):
		if p == 0:
			break
		for j in range(i + 1, n + 1):
			if p == 0:
				break
			else:
				p -= 1
			print(f'{i} {j}')


t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	for i in range(2 * n + p):
		print(i % n + 1, (i + i // n + 1) % n + 1)


t = int(input())
while t:
	t -= 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	count = 0
	for i in range(n - 1):
		over = False
		for j in range(i + 1, n):
			if count < 2 * n + k:
				print(i + 1, j + 1)
				count += 1
			else:
				over = True
				break
		if over:
			break


for t in range(int(input())):
	(n, p) = map(int, input().split())
	(i, j) = (1, 2)
	for k in range(2 * n + p):
		print(i, j)
		j += 1
		if j > n:
			i += 1
			j = i + 1


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
t = int(input())
while t:
	flag = 0
	(n, p) = get_ints()
	count = 0
	i = 1
	while i < n + 1:
		for j in range(i + 1, n + 1):
			print(i, j)
			count += 1
			if count == 2 * n + p:
				flag = 1
				break
		if flag == 1:
			break
		i += 1
	t -= 1


t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	c = 0
	z = 2 * n + p
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if c >= z:
				break
			else:
				print(i, j)
				c = c + 1


a = int(input())
l = []
for j in range(a):
	start = 1
	end = 1
	h = list(map(int, input().split()))
	n = h[0]
	p = h[1]
	for i in range(2 * n + p):
		if end + 1 > n:
			start += 1
			end = start + 1
		else:
			end += 1
		print(start, end)


import os
from io import BytesIO, IOBase
import sys

def main():
	for _ in range(int(input())):
		(n, p) = map(int, input().split())
		ans = []
		for i in range(0, n):
			ans.extend([(i, (i + 1) % n), (i, (i + 2) % n)])
		if p:
			for i in range(n):
				for j in range(i + 3, n - max(2 - i, 0)):
					ans.append((i, j))
					p -= 1
					if not p:
						break
				if not p:
					break
		for (x, y) in ans:
			print(x + 1, y + 1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

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

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(Int()):
	(n, p) = value()
	edges = 0
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if edges < 2 * n + p:
				print(i, j)
				edges += 1


for i in range(int(input())):
	(n, p) = map(int, input().split())
	all = 2 * n + p
	for j in range(1, n + 1):
		for k in range(j + 1, n + 1):
			if all <= 0:
				break
			print(j, k)
			all -= 1
		if all <= 0:
			break


for t in range(int(input())):
	(n, p) = (int(x) for x in input().split())
	g = [[0] * n for i in range(n)]
	for i in range(n):
		g[i][(i + 1) % n] = g[(i + 1) % n][i] = 1
		g[i][(i + 2) % n] = g[(i + 2) % n][i] = 1
	for i in range(n):
		for j in range(i + 1, n):
			if g[i][j] == 0:
				g[i][j] = 1
				p -= 1
			if p <= 0:
				break
		if p <= 0:
			break
	for i in range(n):
		for j in range(i + 1, n):
			if g[i][j] == 1:
				print(i + 1, j + 1)


for _ in range(int(input())):
	(v, p) = [int(x) for x in input().split()]
	counter1 = 1
	counter2 = 1
	counter3 = 0
	while counter3 != 2 * v + p:
		counter3 += 1
		print(counter1, counter2 + counter1)
		counter2 += 1
		if counter2 + counter1 == v + 1:
			counter2 = 1
			counter1 += 1


N = int(input())
for i in range(N):
	a = list(map(int, input().split()))
	c = 0
	for i in range(a[0]):
		if c == 2 * a[0] + a[1]:
			break
		for j in range(i + 1, a[0]):
			if c == 2 * a[0] + a[1]:
				break
			print(i + 1, j + 1)
			c = c + 1


t = int(input())
while t > 0:
	t -= 1
	(n, p) = list(map(int, input().split()))
	count = 0
	for i in range(1, n):
		for j in range(i + 1, n + 1):
			count += 1
			if count <= 2 * n + p:
				print('%s %s' % (i, j))


import sys

def compute(n, p):
	count = 0
	for i in range(1, n + 1, 1):
		for j in range(i + 1, n + 1, 1):
			print('{0} {1}'.format(i, j))
			count += 1
			if count >= 2 * n + p:
				return
t = int(input())
for case in range(t):
	(n, p) = list(map(int, input().split()))
	compute(n, p)


t = int(input())
while t > 0:
	(n, p) = map(int, input().split())
	temp = 2 * n + p
	l = 1
	r = l + 1
	while temp > 0:
		if r == n + 1:
			l += 1
			r = l + 1
		print(l, r)
		r += 1
		temp -= 1
	t -= 1


import sys
input = sys.stdin.readline
read_tuple = lambda _type: map(_type, input().split(' '))

def solve():
	t = int(input())
	for _ in range(t):
		(n, p) = read_tuple(int)
		n_vertices = 2 * n + p
		for i in range(1, n + 1):
			for j in range(i + 1, n + 1):
				if not n_vertices:
					break
				print(i, j)
				n_vertices -= 1
			if not n_vertices:
				break
solve()


import sys
input = lambda : sys.stdin.readline().strip()

def solve(n, p):
	total = 0
	for d in range(1, n):
		for i in range(1, n + 1):
			print(i, (i + d - 1) % n + 1)
			total += 1
			if total == 2 * n + p:
				return
for _ in range(int(input())):
	(n, p) = [int(x) for x in input().split()]
	solve(n, p)


t = int(input())
for tt in range(t):
	(n, p) = map(int, input().split(' '))
	edge_count = 0
	edge_len = 1
	v = 0
	while edge_count < 2 * n + p:
		print('{} {}'.format(v + 1, (v + edge_len) % n + 1))
		v = (v + 1) % n
		edge_count += 1
		if edge_count % n == 0:
			edge_len += 1


import math, sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
lili = lambda : list(map(int, sys.stdin.readlines()))
li = lambda : list(map(int, input().split()))
I = lambda : int(input())
S = lambda : input().strip()
mod = 1000000007
for _ in range(I()):
	(n, p) = li()
	k = 1
	c = k + 1
	p = 2 * n + p
	while p:
		print(k, c)
		p -= 1
		if c == n:
			k += 1
			c = k
		c += 1


t = int(input())
for ignored in range(t):
	(n, p) = list(map(int, input().split()))
	a = [[False] * n for i in range(n)]
	cnt = [0] * n
	for i in range(2 * n + p):
		mini = float('inf')
		minim = float('inf')
		(x, y) = (-1, -1)
		for x1 in range(n):
			for y1 in range(x1 + 1, n):
				if x1 != y1 and (not a[x1][y1]) and (max(cnt[x1], cnt[y1]) < mini or (max(cnt[x1], cnt[y1]) == mini and min(cnt[x1], cnt[y1]) < minim)):
					(x, y) = (x1, y1)
					mini = max(cnt[x1], cnt[y1])
					minim = min(cnt[x1], cnt[y1])
		cnt[x] += 1
		cnt[y] += 1
		a[x][y] = True
		a[y][x] = True
		print(x + 1, y + 1)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	c = a * 2 + b
	for i in range(1, a + 1):
		for j in range(i + 1, a + 1):
			if c == 0:
				break
			print(str(i) + ' ' + str(j))
			c -= 1
		if c == 0:
			break


import re
t = int(input())
for i in range(t):
	x = input()
	x = re.split('\\s', x)
	x1 = int(x[0])
	x2 = int(x[1])
	cnt = 0
	for j in range(x1):
		m = j + 1
		while m < x1:
			print(f'{j + 1} {m + 1}')
			cnt += 1
			m += 1
			if cnt >= 2 * x1 + x2:
				break
		if cnt >= 2 * x1 + x2:
			break


for j in range(int(input())):
	(n, p) = map(int, input().split())
	k = [str(i) + ' ' + str(i + 1) for i in range(1, n)] + ['1 ' + str(n), '1 ' + str(n - 1), '2 ' + str(n)] + [str(i) + ' ' + str(i + 2) for i in range(1, n - 1)]
	for i in range(1, n - 2):
		if p == 0:
			break
		for j in range(i + 3, n + int(i > 1) - (i < 3)):
			k += [str(i) + ' ' + str(j)]
			p -= 1
			if p == 0:
				break
	print('\n'.join(sorted(k)))


t = int(input())
for test in range(t):
	(n, p) = map(int, input().split())
	s = ''
	for i in range(n):
		s += str(i + 1) + ' ' + str((i + 1) % n + 1) + '\n'
		s += str(i + 1) + ' ' + str((i + 2) % n + 1) + '\n'
	if p > 0:
		for i in range(n):
			for j in range(i + 3, min(n, i - 2 + n)):
				s += str(i + 1) + ' ' + str(j + 1) + '\n'
				p -= 1
				if p <= 0:
					break
			if p <= 0:
				break
	print(s, end='')


t = int(input())
for tt in range(t):
	(n, p) = map(int, input().split())
	now = 1
	ans = 0
	while ans != 2 * n + p:
		for i in range(now + 1, n + 1):
			if ans == 2 * n + p:
				break
			print(now, i)
			ans += 1
		now += 1


import sys
input = lambda : sys.stdin.readline().strip()

def solve(n, p):
	total = 0
	used = set()
	for d in range(1, n):
		for i in range(1, n + 1):
			(u, v) = (i, (i + d - 1) % n + 1)
			e = (min(u, v), max(u, v))
			if e not in used:
				used.add(e)
				print(u, v)
				total += 1
			if total == 2 * n + p:
				return
for _ in range(int(input())):
	(n, p) = [int(x) for x in input().split()]
	solve(n, p)


t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if min(j - i, i + n - j) <= 2:
				print(i, j)
			elif p > 0:
				print(i, j)
				p -= 1


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	cnt = 0
	for i in range(1, n + 1):
		if cnt < 2 * n + p:
			for j in range(i, n + 1):
				if i != j and cnt < 2 * n + p:
					print(i, j)
					cnt += 1


t = int(input())

def readints():
	return map(int, input().split(' '))

def solve():
	(n, p) = readints()
	viz = [[0] * n for _ in range(n)]
	for j in range(n):
		viz[0][j] = viz[j][0] = 1
	for j in range(n):
		viz[1][j] = viz[j][1] = 1
	leftover = p + 3
	done = False
	for i in range(n):
		if done:
			break
		for j in range(i + 1, n):
			if viz[i][j] == 1:
				continue
			leftover -= 1
			viz[i][j] = viz[j][i] = 1
			if leftover == 0:
				done = True
				break
	for i in range(n):
		for j in range(i + 1, n):
			if viz[i][j]:
				print(i + 1, j + 1)
for _ in range(t):
	solve()


t = int(input())
for z in range(t):
	(n, p) = [int(x) for x in input().split()]
	cur = 0
	for i in range(1, n):
		j = i + 1
		while j <= n and cur < n * 2 + p:
			print(i, j)
			j += 1
			cur += 1


import os, io
from sys import stdout
import collections
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]

def binomial_coefficient(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def powerOfK(k, max):
	if k == 1:
		return [1]
	if k == -1:
		return [-1, 1]
	result = []
	n = 1
	while n <= max:
		result.append(n)
		n *= k
	return result

def divisors(n):
	i = 1
	result = []
	while i * i <= n:
		if n % i == 0:
			if n / i == i:
				result.append(i)
			else:
				result.append(i)
				result.append(n / i)
		i += 1
	return result

def digitsSum(n):
	if n == 0:
		return 0
	r = 0
	while n > 0:
		r += n % 10
		n //= 10
	return r

def isValid(i, j, n, m):
	return i >= 0 and i < n and (j >= 0) and (j < m)

def print_grid(grid):
	for line in grid:
		print(' '.join(map(str, line)))

def kadane(a, size):
	max_so_far = 0
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far

def prefixSum(arr):
	for i in range(1, len(arr)):
		arr[i] = arr[i] + arr[i - 1]
	return arr

def ceil(n, d):
	if n % d == 0:
		return n // d
	else:
		return n // d + 1
t = int(input())
for _ in range(t):
	(n, p) = list(map(int, input().split()))
	edges = []
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			edges.append((i, j))
	max_edges = n * (n - 1) // 2
	permitted = 2 * n + p
	to_remove = max_edges - permitted
	if to_remove > 0:
		edges = edges[:-to_remove]
	for edge in edges:
		print(edge[0], edge[1])


def graph(n, p):
	threshold = 2 * n + p
	cache = {}
	for i in range(1, n):
		for j in range(0, n):
			node1 = j + 1
			node2 = (j + i) % n + 1
			if (node1, node2) not in cache:
				print(node1, node2)
				threshold -= 1
				cache[node1, node2] = True
				cache[node2, node1] = True
			if threshold == 0:
				return

def readinput():
	tc = int(input())
	for _ in range(tc):
		(n, p) = map(int, input().split(' '))
		graph(n, p)
readinput()