Read problem statements in [Bengali], [Russian], [Mandarin] and [Vietnamese] as well.

Chef is given two integers N and M. Please help Chef find any connected undirected graph G consisting of exactly N vertices and M edges, such that the number of bridges in G is maximized (among all graphs with N vertices and M edges). G cannot have [self-loops] or [multiple edges].

If there is more than one connected undirected graph with the maximum number of bridges, you may print any one of them.

Note:
A [bridge] is an edge whose removal increases the number of connected components of the graph.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each testcase consists of a single line of input, containing two integers N, M - the number of vertices and edges of the graph you must construct.

------ Output Format ------ 

For each test case, output M lines where the i-th line contains two space-separated integers denoting the i-th edge of the graph G you constructed. The edges may be printed in any order, and for each edge the endpoints may be printed in any order.

Note that G must not contain self-loops or multiple edges, and no other graph on N vertices and M edges can contain strictly more bridges than G.

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

$1 ≤ T ≤ 10^{3}$
$2 ≤ N ≤ 10^{3}$
$N-1 ≤ M ≤ \min(N \cdot (N-1)/2, 10^{5})$
- Sum of $N$ over all test cases do not exceed $10^{3}$
- Sum of $M$ over all test cases do not exceed $10^{5}$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
3
4 4
5 4
3 3

----- Sample Output 1 ------ 
1 2
2 3
3 4
1 3
1 2
2 3
3 4
4 5
1 2
2 3
3 1

----- explanation 1 ------ 
Test case $1$: There is exactly $1$ bridge in the graph and it cannot be increased further.

- 

Test case $2$: Since $M=N-1$ and we are required to output a connected graph, the graph will always be a tree and hence have $4$ bridges. Any tree is acceptable here.

- 

Test case $3$: Since $M= N \cdot (N-1) / 2$ our only choice is a complete graph, which has $0$ bridges.

-

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Constructive algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	ans = {}
	for j in range(1, n):
		ans[j] = [j + 1]
	m -= n - 1
	c = 3
	while m != 0 and c < n + 1:
		j = c - 2
		while j > 0:
			if c not in ans[j]:
				ans[j].append(c)
				m -= 1
			if m == 0:
				break
			j -= 1
		c += 1
	for c in ans:
		x = ans[c]
		for j in x:
			print(c, j)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	ans = {}
	for i in range(1, N):
		ans[i] = [i + 1]
	M -= N - 1
	i = 3
	while M != 0 and i < N + 1:
		j = i - 2
		while j > 0:
			if i not in ans[j]:
				ans[j].append(i)
				M -= 1
			if M == 0:
				break
			j -= 1
		i += 1
	for i in ans:
		T = ans[i]
		for j in T:
			print(i, j)


total_input = int(input())
for _ in range(total_input):
	(n, e) = map(int, input().split())
	g = {n: []}
	for i in range(1, n):
		g[i] = [i + 1]
		print(i, i + 1)
		e -= 1
	end = 3
	while e > 0:
		for i in range(1, end):
			if g[i][-1] < end:
				g[i].append(end)
				print(i, end)
				e -= 1
				if e == 0:
					break
		end += 1


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	num_br = 0
	for i in range(N - 1):
		print(i + 1, i + 2)
		num_br += 1
	node_new = 3
	while num_br < M:
		for i in range(1, node_new - 1):
			print(i, node_new)
			num_br += 1
			if num_br >= M:
				break
		node_new += 1


for i in range(int(input())):
	(n, e) = map(int, input().split())
	for i in range(1, n):
		print(i, i + 1)
		e = e - 1
	for i in range(3, n + 1):
		if e < 1:
			break
		for j in range(1, i - 1):
			print(j, i)
			e = e - 1
			if e == 0:
				break


for _ in range(int(input())):
	(n, m) = map(int, input().strip().split(' '))
	m = m - (n - 1)
	for i in range(1, n):
		print(i, i + 1)
	i = 3
	while m > 0:
		for j in range(1, i - 1):
			if m > 0:
				print(j, i)
				m -= 1
		i += 1


from sys import stdin
t = int(stdin.readline().rstrip())
while t > 0:
	(n, m) = map(int, stdin.readline().strip().split(' '))
	m = m - (n - 1)
	for i in range(1, n):
		print(i, i + 1)
	i = 3
	while m > 0:
		for j in range(1, i - 1):
			if m > 0:
				print(j, i)
				m -= 1
		i += 1
	t -= 1


for x in range(int(input())):
	(a, b) = map(int, input().split())
	bridges = a - 1
	b = b - (a - 1)
	for i in range(1, a):
		print(i, i + 1)
	if b > 0:
		for i in range(3, a + 1):
			for j in range(1, i - 1):
				print(i, j)
				b -= 1
				if b <= 0:
					break
			if b <= 0:
				break


for testcase in range(int(input())):
	(n, m) = map(int, input().split())
	m = m - (n - 1)
	for i in range(1, n):
		print(i, i + 1)
	i = 3
	while m > 0:
		for j in range(1, i - 1):
			if m == 0:
				break
			print(j, i)
			m = m - 1
		i = i + 1


t = int(input())
for _ in range(t):
	(v, e) = l = map(int, input().split())
	for i in range(1, v):
		print(i, i + 1)
		e -= 1
	j = 3
	while e != 0:
		i = 1
		while e != 0 and i + 1 != j:
			print(i, j)
			i += 1
			e -= 1
		j += 1


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	for i in range(N - 1):
		print(str(i + 1), str(i + 2))
	m = N - 1
	for a in range(N):
		for b in range(a - 1):
			if m == M:
				continue
			print(b + 1, a + 1)
			m += 1
		if m == M:
			continue


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	for i in range(1, n):
		print(i, i + 1)
	(m, i) = (m - n + 1, 3)
	while m:
		for j in range(1, i - 1):
			if m:
				print(j, i)
			else:
				break
			m -= 1
		i += 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m == n - 1:
		for i in range(m):
			print(i + 1, i + 2)
	elif m == n * (n - 1) // 2:
		print(1, 2)
		for i in range(3, n + 1):
			for j in range(1, i):
				print(i, j)
	else:
		for i in range(n - 1):
			print(i + 1, i + 2)
		m -= n - 1
		for i in range(3, n + 1):
			tobreak = False
			for j in range(1, i - 1):
				print(i, j)
				m -= 1
				if m == 0:
					tobreak = True
					break
			if tobreak:
				break


t = int(input())
while t > 0:
	(n, m) = list(map(int, input().split()))
	m -= n - 1
	for i in range(1, n):
		print(i, i + 1)
	i = 3
	while m > 0:
		for j in range(1, i - 1):
			if m > 0:
				m = m - 1
				print(j, i)
			else:
				break
		i = i + 1
	t = t - 1


t = int(input())
for zz in range(t):
	(n, m) = map(int, input().split())
	(c, x, mm) = (0, 0, 1)
	l = []
	p = n
	for i in range(1, n):
		print(i, i + 1)
		c += 1
	if c != m:
		for i in range(3, n + 1):
			for j in range(1, i):
				if j != i - 1:
					print(i, j)
					c += 1
				if c == m:
					x = 1
					break
			if x == 1:
				break


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	for i in range(n - 1):
		print(i + 1, i + 2)
	m -= n - 1
	j = 3
	while m:
		for k in range(1, j - 1):
			if m == 0:
				break
			print(j, k)
			m -= 1
		j += 1


try:
	from debugger import debug
except ImportError:

	def debug(**kwargs):
		pass
	pass

def FindGraph():
	(n, m) = map(int, input().split())
	for i in range(1, n):
		print(i, i + 1)
		m -= 1
	for i in range(3, n + 1):
		for j in range(i - 2, 0, -1):
			if m == 0:
				return
			print(j, i)
			m -= 1
for _ in range(int(input())):
	FindGraph()


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = {a: []}
	for i in range(1, a):
		c[i] = [i + 1]
		print(i, i + 1)
		b -= 1
	flg = 3
	while b > 0:
		for j in range(1, flg):
			if c[j][-1] < flg:
				c[j].append(flg)
				print(j, flg)
				b -= 1
				if b == 0:
					break
		flg += 1


for _ in range(int(input())):
	(s, g) = map(int, input().split())
	z = {s: []}
	for i in range(1, s):
		z[i] = [i + 1]
		print(i, i + 1)
		g -= 1
	flag = 3
	while g > 0:
		for a in range(1, flag):
			if z[a][-1] < flag:
				z[a].append(flag)
				print(a, flag)
				g -= 1
				if g == 0:
					break
		flag += 1


total_input = int(input())
for _ in range(total_input):
	(N, e) = map(int, input().split())
	g = {N: []}
	for j in range(1, N):
		g[j] = [j + 1]
		print(j, j + 1)
		e -= 1
	end = 3
	while e > 0:
		for j in range(1, end):
			if g[j][-1] < end:
				g[j].append(end)
				print(j, end)
				e -= 1
				if e == 0:
					break
		end += 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	di = {n: []}
	for i in range(1, n):
		di[i] = [i + 1]
		print(i, i + 1)
		m -= 1
	k = 3
	while m > 0:
		for i in range(1, k):
			if di[i][-1] < k:
				di[i].append(k)
				print(i, k)
				m -= 1
				if m == 0:
					break
		k += 1


input_t = int(input())
for _ in range(input_t):
	(n, edge) = map(int, input().split())
	A = {n: []}
	for i in range(1, n):
		A[i] = [i + 1]
		print(i, i + 1)
		edge -= 1
	temp = 3
	while edge > 0:
		for i in range(1, temp):
			if A[i][-1] < temp:
				A[i].append(temp)
				print(i, temp)
				edge -= 1
				if edge == 0:
					break
		temp += 1


inp = int(input())
for _ in range(inp):
	(n, e) = map(int, input().split())
	A = {n: []}
	for i in range(1, n):
		A[i] = [i + 1]
		print(i, i + 1)
		e -= 1
	end = 3
	while e > 0:
		for i in range(1, end):
			if A[i][-1] < end:
				A[i].append(end)
				print(i, end)
				e -= 1
				if e == 0:
					break
		end += 1


for z in range(int(input())):
	(a, b) = map(int, input().split())
	c = {a: []}
	for i in range(1, a):
		c[i] = [i + 1]
		print(i, i + 1)
		b -= 1
	flag = 3
	while b > 0:
		for j in range(1, flag):
			if c[j][-1] < flag:
				c[j].append(flag)
				print(j, flag)
				b -= 1
				if b == 0:
					break
		flag += 1


test = int(input())

def bridge(num, connections):
	for i in range(num - 2):
		if connections > 0:
			print(i + 1, end=' ')
			print(num)
			connections = connections - 1
		else:
			return
	if connections > 0:
		num = num + 1
		bridge(num, connections)
	else:
		return
for case in range(test):
	graph = input().split()
	vertex = int(graph[0])
	edges = int(graph[1])
	connections = edges
	for i in range(1, vertex):
		connections = connections - 1
		print(i, end=' ')
		print(i + 1)
	if connections > 0:
		bridge(3, connections)


def maxBridge(n, m):
	maxE = n * (n - 1) // 2
	if m == maxE:
		for i in range(1, n + 1):
			for j in range(i + 1, n + 1):
				print('{} {}'.format(i, j))
	elif m == n - 1:
		for i in range(1, n):
			print('{} {}'.format(i, i + 1))
	else:
		m = m - (n - 1)
		for i in range(1, n):
			print('{} {}'.format(i, i + 1))
		(l, r) = (1, 3)
		while m > 0:
			print('{} {}'.format(l, r))
			m -= 1
			if r == 3:
				r += 1
			elif r > 3:
				if r - 1 != l + 1:
					l += 1
				else:
					l = 1
					r += 1
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().strip().split(' '))
	maxBridge(n, m)


def max_the_bridge(v, e):
	if e <= v - 1:
		for i in range(1, v):
			if e > 0:
				print(i, i + 1)
				e -= 1
			else:
				return
	elif e == v * ((v - 1) / 2):
		for i in range(1, v + 1):
			for j in range(i + 1, v + 1):
				print(i, j)
		return
	else:
		for i in range(1, v):
			print(i, i + 1)
			e -= 1
		for i in range(3, v + 1):
			for j in range(1, i - 1):
				if e > 0:
					print(i, j)
					e -= 1
				else:
					return
t = int(input())
for _ in range(t):
	(v, e) = [int(ele) for ele in input().split()[:2]]
	max_the_bridge(v, e)


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	dicti = {}
	for i in range(1, n):
		dicti[i] = [i + 1]
		print(i, i + 1)
		m -= 1
	flag = 3
	while m > 0:
		for i in range(1, flag):
			if dicti[i][-1] < flag:
				dicti[i].append(flag)
				print(i, flag)
				m -= 1
				if m == 0:
					break
		flag += 1


import sys
import math
import itertools
from itertools import combinations
from itertools import permutations
t = int(input())
c = True
h = 0
for _ in range(t):
	(a, b) = map(int, input().split())
	data = {a: []}
	for i in range(1, a):
		data[i] = [i + 1]
		print(i, i + 1)
		b = b - 1
	lout = 3
	if a == 0 and b == 0:
		h = 2 * (a + b)
		h += b - 2
		b = h + (a * b - 2)
		print(b)
	while b > 0 and c:
		for i in range(1, lout):
			if data[i][-1] < lout:
				data[i].append(lout)
				print(i, lout)
				b -= 1
				if b == 0:
					h = (a - b) * (b * (2 * a) + 1) + 2
					break
		lout += 1


for _ in range(int(input())):
	(aa, bb) = map(int, input().split())
	cc = {aa: []}
	for i in range(1, aa):
		cc[i] = [i + 1]
		print(i, i + 1)
		bb -= 1
	flag = 3
	while bb > 0:
		for j in range(1, flag):
			if cc[j][-1] < flag:
				cc[j].append(flag)
				print(j, flag)
				bb -= 1
				if bb == 0:
					break
		flag += 1


T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().strip().split()))
	G = {N: []}
	for i in range(1, N):
		G[i] = [i + 1]
		print(i, i + 1)
		M -= 1
	max_connect = 3
	while M > 0:
		for i in range(1, max_connect):
			if G[i][-1] < max_connect:
				G[i].append(max_connect)
				print(i, max_connect)
				M -= 1
			if M == 0:
				break
		max_connect += 1


t = int(input())
for i in range(t):
	(n, e) = map(int, input().split())
	k = {n: []}
	for i in range(1, n):
		k[i] = [i + 1]
		print(i, i + 1)
		e -= 1
	r = 3
	while e > 0:
		for i in range(1, r):
			if k[i][-1] < r:
				k[i].append(r)
				print(i, r)
				e -= 1
				if e == 0:
					break
		r += 1


try:
	total_inp = int(input())
	for _ in range(total_inp):
		(n, e) = map(int, input().split())
		g = {n: []}
		for i in range(1, n):
			g[i] = [i + 1]
			print(i, i + 1)
			e -= 1
		end = 3
		while e > 0:
			for i in range(1, end):
				if g[i][-1] < end:
					g[i].append(end)
					print(i, end)
					e -= 1
					if e == 0:
						break
			end += 1
except:
	pass


total_input = int(input())
for _ in range(total_input):
	(p, q) = map(int, input().split())
	r = {p: []}
	for i in range(1, p):
		r[i] = [i + 1]
		print(i, i + 1)
		q -= 1
	en = 3
	while q > 0:
		for i in range(1, en):
			if r[i][-1] < en:
				r[i].append(en)
				print(i, en)
				q -= 1
				if q == 0:
					break
		en += 1


import sys
import math
import re
from collections import Counter
from bisect import bisect_left

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def computeXOR(n):
	if n % 4 == 0:
		return n
	if n % 4 == 1:
		return 1
	if n % 4 == 2:
		return n + 1
	return 0

def dell(dict, n, m):
	p = 3
	for i in range(1, n):
		m -= 1
		print(i, i + 1)
		dict[i] = [i + 1]
	while m > 0:
		for i in range(1, p):
			if dict[i][-1] < p:
				dict[i].append(p)
				print(i, p)
				m -= 1
				if m == 0:
					break
		p += 1
t = int(input())
mod = pow(10, 9) + 7
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	dict = {n: []}
	dell(dict, n, m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	res = {n: []}
	for i in range(1, n):
		res[i] = [i + 1]
		print(i, i + 1)
		m -= 1
	flg = 3
	while m > 0:
		for j in range(1, flg):
			if res[j][-1] < flg:
				res[j].append(flg)
				print(j, flg)
				m -= 1
				if m == 0:
					break
		flg += 1


t = int(input())
while t:
	(vertices, edge) = map(int, input().split())
	dic = dict()
	for i in range(1, vertices):
		dic[i] = [i + 1]
		print(i, i + 1)
		edge = edge - 1
	t1 = 3
	while edge > 0:
		for i in range(1, t1):
			if dic[i][-1] < t1:
				dic[i].append(t1)
				print(i, t1)
				edge = edge - 1
			if edge == 0:
				break
		t1 = t1 + 1
	t = t - 1


for q in range(int(input())):
	(a, b) = map(int, input().split())
	c = {a: []}
	for i in range(1, a):
		c[i] = [i + 1]
		print(i, i + 1)
		b = b - 1
	f = 3
	while b > 0:
		for j in range(1, f):
			if c[j][-1] < f:
				c[j].append(f)
				print(j, f)
				b = b - 1
				if b == 0:
					break
		f += 1


for i in range(int(input())):
	(n, m) = map(int, input().split())
	d = {n: []}
	for j in range(1, n):
		d[j] = [j + 1]
		print(j, j + 1)
		m -= 1
	x = 3
	while m > 0:
		for j in range(1, x):
			if d[j][-1] < x:
				d[j].append(x)
				print(j, x)
				m -= 1
				if m == 0:
					break
		x += 1