You are given an undirected unweighted connected graph consisting of $n$ vertices and $m$ edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Your task is to find any spanning tree of this graph such that the maximum degree over all vertices is maximum possible. Recall that the degree of a vertex is the number of edges incident to it.


-----Input-----

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$) — the number of vertices and edges, respectively.

The following $m$ lines denote edges: edge $i$ is represented by a pair of integers $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$), which are the indices of vertices connected by the edge. There are no loops or multiple edges in the given graph, i. e. for each pair ($v_i, u_i$) there are no other pairs ($v_i, u_i$) or ($u_i, v_i$) in the list of edges, and for each pair $(v_i, u_i)$ the condition $v_i \ne u_i$ is satisfied.


-----Output-----

Print $n-1$ lines describing the edges of a spanning tree such that the maximum degree over all vertices is maximum possible. Make sure that the edges of the printed spanning tree form some subset of the input edges (order doesn't matter and edge $(v, u)$ is considered the same as the edge $(u, v)$).

If there are multiple possible answers, print any of them.


-----Examples-----
Input
5 5
1 2
2 3
3 5
4 3
1 5

Output
3 5
2 1
3 2
3 4

Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4

Output
4 1
1 2
1 3

Input
8 9
1 2
2 3
2 5
1 6
3 4
6 5
4 5
2 7
5 8

Output
3 2
2 5
8 5
6 1
2 7
1 2
3 4



-----Note-----

Picture corresponding to the first example: [Image]

In this example the number of edges of spanning tree incident to the vertex $3$ is $3$. It is the maximum degree over all vertices of the spanning tree. It is easy to see that we cannot obtain a better answer.

Picture corresponding to the second example: [Image]

In this example the number of edges of spanning tree incident to the vertex $1$ is $3$. It is the maximum degree over all vertices of the spanning tree. It is easy to see that we cannot obtain a better answer.

Picture corresponding to the third example: [Image]

In this example the number of edges of spanning tree incident to the vertex $2$ is $4$. It is the maximum degree over all vertices of the spanning tree. It is easy to see that we cannot obtain a better answer. But because this example is symmetric, we can choose almost the same spanning tree but with vertex $5$ instead of $2$.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Starter code:

Solutions:
(n, m) = map(int, input().split())
ar = [[] for i in range(n + 1)]
mx = [0] * (n + 1)
for i in range(m):
	(x, y) = map(int, input().split())
	mx[x] += 1
	mx[y] += 1
	ar[x].append(y)
	ar[y].append(x)
st = mx.index(max(mx))
used = [False] * (n + 1)
ans = []
q = []
used[st] = True

def bfs(st, tt=0):
	q.append(st)
	while tt < len(q):
		v = q[tt]
		for i in ar[v]:
			if not used[i]:
				used[i] = True
				q.append(i)
				ans.append((v, i))
		tt += 1
bfs(st)
for i in ans:
	print(' '.join(map(str, i)))


(n, m) = map(int, input().strip().split())
l = [[] for i in range(n + 1)]
count = [0 for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().strip().split())
	l[a].append(b)
	l[b].append(a)
	count[a] += 1
	count[b] += 1
mx = 0
v = -1
for i in range(n + 1):
	if count[i] > mx:
		mx = count[i]
		v = i
layer = l[v]
used = [False for i in range(n + 1)]
used[v] = True
for i in l[v]:
	print(v, i)
	used[i] = True
while layer != []:
	newlayer = []
	for i in layer:
		for j in l[i]:
			if used[j] == False:
				print(i, j)
				newlayer.append(j)
				used[j] = True
	layer = newlayer


(n, m) = map(int, input().split())
dl = [0] * (n + 1)
cl = []
g = [list() for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
	dl[u] += 1
	dl[v] += 1
	cl.append((u, v))
pos = dl.index(max(dl))
dl = [0] * (n + 1)
queue = []
dl[pos] = 1
for u in g[pos]:
	print(pos, u)
	queue.append(u)
	dl[u] = 1
for u in queue:
	for v in g[u]:
		if dl[v] != 1:
			print(u, v)
			dl[v] = 1
			queue.append(v)


(n, m) = [int(x) for x in input().split()]
graph = {}
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	for (a, b) in ((a, b), (b, a)):
		if a not in graph:
			graph[a] = [b]
		else:
			graph[a].append(b)

def tree(new):
	total = []
	for v in new:
		for item in graph[v]:
			if item not in invite:
				total.append((v, item))
				invite.add(item)
				new.append(item)
	return total
index = max_rou = 0
for v in graph:
	if len(graph[v]) > max_rou:
		max_rou = len(graph[v])
		index = v
invite = set([index])
answer = tree([index])
for i in range(n - 1):
	print(*answer[i])


from collections import deque

def bfs(a, x):
	vis = [0] * (n + 1)
	queue = deque()
	queue.append(x)
	vis[x] = 1
	b = []
	while queue:
		s = queue.pop()
		for i in a[s]:
			if vis[i] == 0:
				b.append([s, i])
				queue.append(i)
				vis[i] = 1
	return b
(n, m) = list(map(int, input().split()))
a = [[] for i in range(n + 1)]
for i in range(m):
	(b, c) = list(map(int, input().split()))
	a[b].append(c)
	a[c].append(b)
b = []
for i in range(n + 1):
	b.append(len(a[i]))
c = b.index(max(b))
d = bfs(a, c)
for i in range(len(d)):
	print(*d[i])


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter, OrderedDict
import threading
from math import gcd

def main():
	(n, m) = map(int, input().split())
	adj = [[] for _ in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	max_degree = [-1, -1]
	for i in range(n):
		if len(adj[i]) > max_degree[0]:
			max_degree = [len(adj[i]), i]
	visit = [0] * n
	q = deque([max_degree[1]])
	visit[max_degree[1]] = 1
	while q:
		x = q.popleft()
		for nx in adj[x]:
			if not visit[nx]:
				q.append(nx)
				visit[nx] = 1
				print(x + 1, nx + 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()


class Item:

	def __init__(self, k):
		self.k = k
		self.free = True
		self.next = []

	def bind(self, other):
		self.next.append(other)
		other.next.append(self)
(n, m) = map(int, input().split())
items = [Item(i) for i in range(1, n + 1)]
for _ in range(m):
	(x, y) = map(int, input().split())
	items[x - 1].bind(items[y - 1])
s = max(items, key=lambda x: len(x.next))
s.free = False
q = [s]
while q:
	cur = q.pop()
	for nxt in cur.next:
		if nxt.free:
			print(cur.k, nxt.k)
			nxt.free = False
			q.append(nxt)


from collections import defaultdict, deque
(n, m) = map(int, input().split())
g = defaultdict(list)
for _ in range(m):
	(x, y) = map(int, input().split())
	g[x].append(y)
	g[y].append(x)
max_deg = 0
for i in g:
	if len(g[i]) > max_deg:
		max_deg = len(g[i])
		v = i
q = deque()
ans = []
visited = [False] * (n + 1)
q.append(v)
visited[v] = True
while q:
	s = q.popleft()
	for i in g[s]:
		if not visited[i]:
			ans.append((s, i))
			q.append(i)
			visited[i] = True
for i in ans:
	print(*i)


from collections import defaultdict, deque
(n, m) = map(int, input().split())
g = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
max_node = 1
for node in g:
	if len(g[node]) > len(g[max_node]):
		max_node = node
q = deque()
vis = set()
vis.add(max_node)
ans = []
for node in g[max_node]:
	q.append(node)
	vis.add(node)
	ans.append((max_node, node))
while q:
	node = q.popleft()
	for child in g[node]:
		if child not in vis:
			vis.add(child)
			q.append(child)
			ans.append((node, child))
for (u, v) in ans:
	print(u, v)


from collections import deque
(n, m) = list(map(int, input().split()))
a = []
rinsetu = [[] for i in range(n + 1)]
count = [0 for i in range(n + 1)]
for i in range(m):
	(u, v) = list(map(int, input().split()))
	count[u] += 1
	count[v] += 1
	a.append([u, v])
	rinsetu[u].append(v)
	rinsetu[v].append(u)
root = count.index(max(count))
visitflag = [0 for i in range(n + 1)]
queue = deque([root])
while len(queue) > 0:
	now = queue.popleft()
	for i in rinsetu[now]:
		if visitflag[i] == 0:
			visitflag[i] = now
			queue.append(i)
for i in range(1, n + 1):
	if i == root:
		continue
	else:
		print(i, visitflag[i])


from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(10 ** 5)
from collections import defaultdict

def find(a):
	if a == par[a]:
		return a
	par[a] = find(par[a])
	return par[a]

def union(a, b):
	par_a = find(a)
	par_b = find(b)
	if par_b == par_a:
		return 0
	if sz[par_a] > sz[par_b]:
		par[par_b] = par_a
		sz[par_a] += sz[par_b]
	else:
		par[par_a] = par_b
		sz[par_b] += sz[par_a]
	return 1
for _ in range(1):
	(n, eg) = list(map(int, stdin.readline().split()))
	g = defaultdict(list)
	for i in range(eg):
		(A, B) = list(map(int, stdin.readline().split()))
		g[A] += [B]
		g[B] += [A]
	(mx, mx_deg) = (0, 1)
	for (node, nl) in g.items():
		if len(nl) >= mx:
			mx = len(nl)
			mx_deg = node
	par = [i for i in range(n + 1)]
	sz = [1] * (1 + n)
	ans = []
	for neigh in g[mx_deg]:
		union(neigh, mx_deg)
		ans += [[neigh, mx_deg]]
	for (src, ll) in g.items():
		for neigh in ll:
			if union(src, neigh) == 1:
				ans += [[neigh, src]]
	for (x, y) in ans:
		print(x, y)


import sys
input = sys.stdin.buffer.readline

def find(x):
	if par[x] == x:
		return x
	par[x] = find(par[x])
	return par[x]

def union(a, b):
	xa = find(a)
	xb = find(b)
	if xa == xb:
		return 0
	if size[xa] > size[xb]:
		(xa, xb) = (xb, xa)
	par[xa] = xb
	return 1
(n, m) = map(int, input().split())
stored = [0 for i in range(n + 1)]
graph = [[] for i in range(n + 1)]
size = [1 for i in range(n + 1)]
par = [i for i in range(n + 1)]
collect = []
for i in range(m):
	(a, b) = map(int, input().split())
	stored[a] += 1
	stored[b] += 1
	graph[a].append(b)
	graph[b].append(a)
	collect.append([a, b])
(maxi, store) = (0, 0)
for i in range(1, n + 1):
	if maxi < stored[i]:
		maxi = stored[i]
		store = i
last = []
for i in graph[store]:
	union(i, store)
	last.append([i, store])
for i in range(m):
	if union(collect[i][0], collect[i][1]):
		last.append([collect[i][0], collect[i][1]])
for i in last:
	print(i[0], i[1])
print()


(n, m) = list(map(int, input().split()))
g = [[] for i in range(n + 1)]
for i in range(m):
	(u, v) = list(map(int, input().split()))
	g[u].append(v)
	g[v].append(u)
root = 0
for i in range(1, n + 1):
	if len(g[i]) > len(g[root]):
		root = i
from collections import deque
visited = [False for i in range(n + 1)]
q = deque([root])
visited[root] = True
while len(q) > 0:
	u = q.popleft()
	for v in g[u]:
		if not visited[v]:
			q.append(v)
			print(u, v)
			visited[v] = True


import sys

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = sys.stdin.readline().split()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_int(self):
		return int(self.next())

	def solve(self):
		n = self.next_int()
		m = self.next_int()
		es = [(self.next_int() - 1, self.next_int() - 1) for _ in range(0, m)]
		dd = [0 for _ in range(0, n)]
		for e in es:
			dd[e[0]] += 1
			dd[e[1]] += 1
		ii = 0
		for i in range(0, n):
			if dd[i] > dd[ii]:
				ii = i
		fa = [-1 for _ in range(0, n)]
		for e in filter(lambda x: x[0] == ii or x[1] == ii, es):
			print(e[0] + 1, e[1] + 1)
			fa[e[0] + e[1] - ii] = ii
		for e in es:
			a = self.find(e[0], fa)
			b = self.find(e[1], fa)
			if a != b:
				fa[a] = b
				print(e[0] + 1, e[1] + 1)

	def find(self, k, fa):
		if fa[k] == -1:
			return k
		fa[k] = self.find(fa[k], fa)
		return fa[k]
Main().solve()


from collections import deque

def main():
	(n, m) = map(int, input().split())
	adj = [[] for _ in range(n)]
	for i in range(m):
		(a, b) = map(int, input().split())
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	maxDeg = 0
	maxDegV = -1
	for i in range(n):
		if maxDeg < len(adj[i]):
			maxDeg = len(adj[i])
			maxDegV = i
	used = [False] * n
	q = deque([], n + 100)

	def bfs(v0):
		used[v0] = True
		q.append(v0)
		while q:
			u = q.popleft()
			for v in adj[u]:
				if not used[v]:
					q.append(v)
					print(u + 1, v + 1)
					used[v] = True
	bfs(maxDegV)
main()


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

def main():

	def union(u, v):
		p = find(u)
		q = find(v)
		if p == q:
			return
		if rank[p] < rank[q]:
			(p, q) = (q, p)
		parent[q] = p
		if rank[p] == rank[q]:
			rank[p] += 1

	def find(v):
		if parent[v] == v:
			return v
		else:
			p = find(parent[v])
			parent[v] = p
			return p
	(V, E) = map(int, input().split())
	parent = list(range(V))
	rank = [0] * V
	g = [set() for _ in range(V)]
	for _ in range(E):
		(u, v) = map(int, input().split())
		g[u - 1].add(v - 1)
		g[v - 1].add(u - 1)
	max_deg_v = max(range(V), key=lambda i: len(g[i]))
	mst = []
	for v in g[max_deg_v]:
		union(v, max_deg_v)
		mst.append((v, max_deg_v))
	for u in range(V):
		for v in g[u]:
			if len(mst) >= V - 1:
				break
			if find(u) != find(v):
				union(u, v)
				mst.append((u, v))
	for (u, v) in mst:
		print(u + 1, v + 1)
main()


import sys
from collections import Counter, defaultdict

def i_ints():
	return map(int, sys.stdin.readline().split())
(n, m) = i_ints()
E = defaultdict(set)
for i in range(m):
	(u, v) = i_ints()
	E[u].add(v)
	E[v].add(u)

def append_edge(u, v):
	E[u].discard(v)
	E[v].discard(u)
	t.add(u)
	t.add(v)
	te.append((u, v))

def complete_tree(u):
	todo = {u}
	while todo:
		u = todo.pop()
		starts = list(E[u])
		for v in starts:
			if v not in t:
				append_edge(u, v)
				todo.add(v)

def print_tree():
	for (u, v) in te:
		print(u, v)
u0 = max(E, key=lambda u: len(E[u]))
t = {u0}
te = []
starts = list(E[u0])
for v in starts:
	append_edge(u0, v)
for v in starts:
	complete_tree(v)
print_tree()


(n, m) = map(int, input().split())
adj = [0] * (n + 1)
for i in range(n + 1):
	adj[i] = []
s = 0
for i in range(m):
	(x, y) = map(int, input().split())
	adj[x].append(y)
	adj[y].append(x)
	if len(adj[x]) > len(adj[s]):
		s = x
	if len(adj[y]) > len(adj[s]):
		s = y
stk = []
mp = {}
mp[s] = 1
for i in range(len(adj[s])):
	stk.append([s, adj[s][i]])
	if adj[s][i] not in mp:
		mp[adj[s][i]] = 1
i = 0
while i < len(stk):
	k = stk[i][1]
	for j in range(len(adj[k])):
		if k not in mp or adj[k][j] not in mp:
			stk.append([k, adj[k][j]])
			mp[k] = 1
			mp[adj[k][j]] = 1
	i += 1
for i in range(len(stk)):
	print(*stk[i])


[n, m, d] = [int(x) for x in input().split()]
gr = []

def read_edge():
	[a, b] = [int(x) for x in input().split()]
	if a == 1 or b == 1:
		gr.append(a + b - 1)
	return [a, b]
edges = [read_edge() for i in range(m)]
par = [i for i in range(0, n + 1)]
rank = [0 for i in range(0, n + 1)]

def find_parent(a):
	if par[a] == a:
		return a
	par[a] = find_parent(par[a])
	return par[a]

def union_sets(a, b):
	a = find_parent(a)
	b = find_parent(b)
	if a != b:
		if rank[b] > rank[a]:
			[b, a] = [a, b]
		par[b] = a
		if rank[a] == rank[b]:
			rank[a] += 1
		return True
	return False
if d > len(gr):
	print('NO')
else:
	for [a, b] in edges:
		if a != 1 and b != 1:
			union_sets(a, b)
	components = sum([par[i] == i for i in range(2, n + 1)])
	if components > d:
		print('NO')
	else:
		par2 = [find_parent(i) for i in range(0, n + 1)]
		par = [i for i in range(0, n + 1)]
		rank = [0 for i in range(0, n + 1)]
		print('YES')
		s = set()
		h = set()
		for x in gr:
			if not par2[x] in s:
				s.add(par2[x])
				h.add(x)
				print('1 %d' % x)
				union_sets(1, x)
		total = components
		for x in gr:
			if total == d:
				break
			if not x in h:
				print('1 %d' % x)
				union_sets(1, x)
				total += 1
		for [a, b] in edges:
			if a != 1 and b != 1:
				if union_sets(a, b):
					print('%d %d' % (a, b))


import sys
from collections import defaultdict, deque
import math
(n, m) = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
for i in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	graph[u].append(v)
	graph[v].append(u)
ans = -1
deg = 0
for i in graph:
	if len(graph[i]) > deg:
		deg = len(graph[i])
		ans = i
vis = defaultdict(int)
q = deque()
q.append(ans)
vis[ans] = 1
while q:
	a = q.popleft()
	for j in graph[a]:
		if vis[j] == 0:
			vis[j] = 1
			print(a, j)
			q.append(j)


(n, m) = list(map(int, input().split()))
adj = {}
nincident = [0] * (n + 1)
edges = []
for i in range(1, n + 1):
	adj[i] = []
for i in range(m):
	(u, v) = list(map(int, input().split()))
	edges.append((u, v))
	adj[u].append(v)
	adj[v].append(u)
	nincident[u] += 1
	nincident[v] += 1
vmax = 0
for v in range(1, n + 1):
	if nincident[v] > nincident[vmax]:
		vmax = v
result = []
rank = [0] * (n + 1)
parent = [0] * (n + 1)

def make_set(i):
	rank[i] = 0
	parent[i] = i

def find_set(i):
	if i != parent[i]:
		parent[i] = find_set(parent[i])
	return parent[i]

def union_op(x, y):
	s_x = find_set(x)
	s_y = find_set(y)
	if rank[s_x] < rank[s_y]:
		parent[s_x] = s_y
	else:
		parent[s_y] = s_x
		if rank[s_y] == rank[s_x]:
			rank[s_x] += 1
for i in range(1, n + 1):
	make_set(i)
for u in adj[vmax]:
	result.append((u, vmax))
	union_op(u, vmax)
for e in edges:
	if find_set(e[0]) != find_set(e[1]):
		result.append(e)
		union_op(e[0], e[1])
for e in result:
	print(e[0], e[1])


import sys

def rint():
	return map(int, sys.stdin.readline().split())
(n, m) = rint()
e = [set() for i in range(n + 1)]
for i in range(m):
	(a, b) = rint()
	e[a].add(b)
	e[b].add(a)
m = 0
mi = 0
for i in range(1, n + 1):
	l = len(e[i])
	if l > m:
		mi = i
		m = l
v = [0 for i in range(n + 1)]
v[0] = 1
ni = mi
ans = []
stack = [ni]
v[ni] = 1
while len(stack):
	ni = stack.pop()
	for nn in e[ni]:
		if v[nn]:
			continue
		else:
			v[nn] = 1
			ans.append([ni, nn])
			stack.append(nn)
for e in ans:
	print(*e)


def dfs(s):
	(stk, cnt) = ([], [])
	stk.append(s)
	cnt.append(0)
	while len(stk) > 0:
		s = stk[-1]
		ll = cnt[-1]
		visit[s] = 1
		flag = 1
		for j in range(ll, len(adj[s]), 1):
			if visit[adj[s][j]] == 0:
				cnt[-1] = j + 1
				stk.append(adj[s][j])
				cnt.append(0)
				flag = 0
				break
		if flag:
			stk.pop()
			cnt.pop()
(n, m, d) = map(int, input().split())
adj = [0] * (n + 1)
for i in range(n + 1):
	adj[i] = []
for i in range(m):
	(x, y) = map(int, input().split())
	adj[x].append(y)
	adj[y].append(x)
visit = [0] * (n + 1)
visit[1] = 1
ans = [0] * m
ct = 0
mark = [0] * (n + 1)
mark[1] = 1
for l in range(len(adj[1])):
	i = adj[1][l]
	if visit[i] == 0:
		dfs(i)
		ans[ct] = [1, i]
		mark[i] = 1
		ct += 1
if ct > d:
	print('NO')
	exit()
if ct < d:
	for i in range(len(adj[1])):
		if mark[adj[1][i]] == 0:
			ans[ct] = [1, adj[1][i]]
			mark[adj[1][i]] = 1
			ct += 1
		if ct == d:
			break
	if ct < d:
		print('NO')
		exit()
i = 0
while i < ct:
	k = ans[i][1]
	if visit[k]:
		for j in range(len(adj[k])):
			if mark[adj[k][j]] == 0:
				mark[adj[k][j]] = 1
				ans[ct] = [k, adj[k][j]]
				ct += 1
		visit[k] = 0
	i += 1
print('YES')
for i in range(ct):
	print(*ans[i])


class Union:

	def __init__(self):
		self.parent = -1
		self.rank = 1

	def Find(self):
		if self.parent == -1:
			return self
		return self.parent.Find()

	def Unite(self, Node):
		(L, R) = (self.Find(), Node.Find())
		if L == R:
			return 0
		if L.rank < R.rank:
			L.parent = R
		elif L.rank > R.rank:
			R.parent = L
		else:
			(L.parent, R.rank) = (R, R.rank + 1)
		return 1
(n, m) = input().split()
(n, m) = (int(n), int(m))
edges = []
for i in range(m):
	edges.append(list(map(int, input().split())))
degree = {}
Vertex = {}
for i in range(1, n + 1):
	Vertex[i] = Union()
for (u, v) in edges:
	(degree[u], degree[v]) = (degree.get(u, 0) + 1, degree.get(v, 0) + 1)
Max = 1
for node in degree:
	if degree[node] > degree[Max]:
		Max = node
(e1, e2) = ([], [])
for (u, v) in edges:
	if u == Max or v == Max:
		e1.append([u, v])
	else:
		e2.append([u, v])
edges = e1 + e2 + []
for i in range(len(edges)):
	(u, v) = (edges[i][0], edges[i][1])
	if Vertex[u].Unite(Vertex[v]) == 1:
		print(*edges[i])


import sys
input = sys.stdin.readline
from math import *
from collections import deque
(n, m) = map(int, input().split())
a = [[] for i in range(n + 1)]
vis = [0 for i in range(n + 1)]
b = []
for i in range(m):
	(x, y) = map(int, input().split())
	a[x].append(y)
	a[y].append(x)
for i in range(1, n + 1):
	b.append([len(a[i]), i])
b.sort(reverse=True)
r = []

def bfs(i):
	q = deque()
	q.append(i)
	vis[i] = 1
	while len(q) > 0:
		z = q.popleft()
		for j in a[z]:
			if vis[j] == 0:
				vis[j] = 1
				q.append(j)
				r.append([z, j])
bfs(b[0][1])
for i in r:
	print(*i)


import os
import sys
from io import BytesIO, IOBase
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')
import sys, threading
sys.setrecursionlimit(400000)
threading.stack_size(10 ** 8)

def dfs(x, y, t):
	global v, l1, l2, adj, d, ans, l3, c
	v[x] = 1
	l1[x] = t
	l2[x] = t
	for i in adj[x]:
		if not v[i]:
			if x == 1:
				c += 1
			dfs(i, x, t + 1)
			if l2[i] <= l1[x]:
				l2[x] = l2[i]
				ans.append([x, i])
				if x == 1:
					d -= 1
			else:
				ans.append([x, i])
				if x == 1:
					d -= 1
		elif i != y:
			if l2[i] < l1[x]:
				l2[x] = l2[i]
				if i == 1:
					l3.append([x, (y, x)])

def main():
	global v, l1, l2, adj, d, ans, l3, c
	(n, m, d) = map(int, input().split())
	d1 = d
	adj = [[] for i in range(n + 1)]
	v = [0] * (n + 1)
	l1 = [0] * (n + 1)
	l2 = [0] * (n + 1)
	l3 = []
	ans = []
	c = 0
	for i in range(m):
		(x, y) = map(int, input().split())
		adj[x].append(y)
		adj[y].append(x)
	if len(adj[1]) < d:
		print('NO')
	else:
		dfs(1, 0, 0)
		a = 'YES'
		from collections import defaultdict
		dd = defaultdict(int)
		if c > d1:
			a = 'NO'
		elif c < d1:
			for i in l3:
				if d == 0:
					break
				ans.append([1, i[0]])
				dd[i[1]] = 1
				d -= 1
		print(a)
		if a == 'YES':
			for i in ans:
				(x, y) = i
				if dd[x, y] == 0:
					print(*i)
t = threading.Thread(target=main)
t.start()
t.join()


from collections import deque

def bfs(start):
	visited = [False] * (nVertexes + 1)
	visited[start] = True
	q = deque()
	q.append(start)
	while q:
		curV = q.popleft()
		for nextV in edges[curV]:
			if not visited[nextV]:
				visited[nextV] = True
				print('%d %d' % (curV, nextV))
				q.append(nextV)
(nVertexes, nEdges) = map(int, input().split())
edges = [[] for _ in range(nVertexes + 1)]
for _ in range(nEdges):
	(u, v) = map(int, input().split())
	edges[u].append(v)
	edges[v].append(u)
start = edges.index(max(edges, key=len))
bfs(start)


def main():
	(n, m) = map(int, input().split())
	graph = [None] * n
	center = (None, 0)
	for _ in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		if graph[u]:
			graph[u].append(v)
		else:
			graph[u] = [v]
		if graph[v]:
			graph[v].append(u)
		else:
			graph[v] = [u]
		if len(graph[u]) > center[1]:
			center = (u, len(graph[u]))
		if len(graph[v]) > center[1]:
			center = (v, len(graph[v]))
	visited = {center[0]}
	to_do = [center[0]]
	z = 0
	while z < len(to_do):
		node = to_do[z]
		for conn in graph[node]:
			if conn in visited:
				continue
			visited.add(conn)
			to_do.append(conn)
			print(node + 1, conn + 1)
		z += 1
main()


def digraph_from_input():
	digraph = dict()
	(n, m) = map(int, input().split())
	for t in range(m):
		(z1, z2) = map(int, input().split())
		if z1 not in digraph:
			digraph[z1] = set([z2])
		else:
			digraph[z1].add(z2)
		if z2 not in digraph:
			digraph[z2] = set([z1])
		else:
			digraph[z2].add(z1)
	return digraph

def BFC(digraph, v):
	s2 = set()
	s1 = set()
	oboid = set()
	ans = dict()
	havepa = set()
	havepa.add(v)
	s1.add(v)
	while s1 != set():
		for element in s1:
			last_element = element
			if element not in oboid:
				oboid.add(element)
				for key in digraph[element]:
					if key not in havepa:
						s2.add(key)
						havepa.add(key)
						ans[key] = last_element
		s1 = s2
		s2 = set()
	return ans
digraph = digraph_from_input()
v = 1
for i in digraph:
	if len(digraph[i]) > len(digraph[v]):
		v = i
q = BFC(digraph, v)
for i in q:
	print(i, q[i])


(n, m, d) = map(int, input().split())
g = [[] for _ in range(n + 1)]
haveOne = [False] * (n + 1)
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
	if u == 1:
		haveOne[v] = True
	if v == 1:
		haveOne[u] = True
count = 0
group = [-1] * (n + 1)
selectedOne = []
for i in range(2, n + 1):
	if group[i] == -1:
		group[i] = count
		useOne = False
		if haveOne[i]:
			selectedOne.append(i)
			useOne = True
		if count >= d:
			count += 1
			break
		incount = count + 1
		qu = []
		qu += g[i]
		while len(qu) > 0:
			c = qu.pop()
			if c != 1 and group[c] == -1:
				if haveOne[c] and (not useOne):
					selectedOne.append(c)
					useOne = True
				group[c] = count
				qu += g[c]
		count += 1
if count > d or d > len(g[1]):
	print('NO')
else:
	diffOne = list(set(g[1]) - set(selectedOne))
	diffOne = selectedOne + diffOne
	g[1] = diffOne[:d]
	visited = [False] * (n + 1)
	qVisit = [1]
	visited[1] = True
	print('YES')
	while len(qVisit) > 0:
		i = qVisit.pop()
		for j in g[i]:
			if not visited[j]:
				print(i, j)
				visited[j] = True
				qVisit.append(j)


from collections import deque as queue
(n, m) = list(map(int, input().split()))
used = [0] * n
edges = [[] for _ in range(n)]
a = []
q = queue(a, 200000)

def bfs(z):
	used[z] = 1
	q.append(z)
	while q:
		x = q.popleft()
		for i in edges[x]:
			if not used[i]:
				q.append(i)
				print(x + 1, i + 1)
				used[i] = 1
for i in range(m):
	(a, b) = list(map(int, input().split()))
	edges[a - 1].append(b - 1)
	edges[b - 1].append(a - 1)
k = 0
for i in range(n):
	k = max(k, len(edges[i]))
for i in range(n):
	if len(edges[i]) == k:
		bfs(i)
		break


import os
import sys
from io import BytesIO, IOBase
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')
from collections import deque

def bfs(x):
	global v, ans, adj
	q = deque([])
	v[x] = 1
	q.append(x)
	while len(q):
		cur = q.popleft()
		for i in adj[cur]:
			if not v[i]:
				v[i] = 1
				ans.append([cur, i])
				q.append(i)
(n, m) = map(int, input().split())
v = [0] * (n + 1)
ans = []
adj = [[] for i in range(n + 1)]
z = [0, 1]
for i in range(m):
	(x, y) = map(int, input().split())
	adj[x].append(y)
	adj[y].append(x)
	if len(adj[x]) >= len(adj[y]) and len(adj[x]) > z[0]:
		z = [len(adj[x]), x]
	elif len(adj[y]) > len(adj[x]) and len(adj[y]) > z[0]:
		z = [len(adj[y]), y]
bfs(z[1])
for i in ans:
	print(*i)


import sys
root = 0
(n, m, D) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
if len(g[root]) < D:
	print('NO')
	sys.exit(0)
uf = [-1 for _ in range(n)]

def find(uf, u):
	if uf[u] < 0:
		return u
	else:
		ans = find(uf, uf[u])
		uf[u] = ans
		return ans

def merge(uf, u, v):
	pu = find(uf, u)
	pv = find(uf, v)
	if pu == pv:
		return
	if uf[pu] > uf[pv]:
		(pu, pv) = (pv, pu)
	uf[pu] += uf[pv]
	uf[pv] = pu
ans = []
in_tree = {}
for v in g[root]:
	merge(uf, root, v)
for i in range(n):
	for v in g[i]:
		if find(uf, i) != find(uf, v):
			merge(uf, i, v)
			ans.append((i + 1, v + 1))
			in_tree[min(i, v), max(i, v)] = True
children = [[] for _ in range(n)]
par = [-1 for _ in range(n)]

def dfs(s, super_p):
	st = [(s, root)]
	while len(st) > 0:
		(u, p) = st.pop()
		children[super_p].append(u)
		merge(par, u, super_p)
		for v in g[u]:
			if v != p and (min(u, v), max(u, v)) in in_tree:
				st.append((v, u))
for v in g[root]:
	dfs(v, v)
sz = len(g[root])
for i in range(len(g[root])):
	found = False
	u = g[root][i]
	if sz > D:
		for v in children[u]:
			for w in g[v]:
				if not found and w != root and (find(par, w) != find(par, v)) and ((min(v, w), max(v, w)) not in in_tree):
					sz -= 1
					found = True
					merge(par, v, w)
					ans.append((v + 1, w + 1))
					in_tree[min(v, w), max(v, w)] = True
	if not found:
		ans.append((root + 1, u + 1))
if sz != D:
	print('NO')
else:
	print('YES')
	print('\n'.join(map(lambda x: '{} {}'.format(x[0], x[1]), ans)))


import collections
(n, m) = [int(x) for x in input().split()]
G = []
for _ in range(n):
	G.append([])
for _ in range(m):
	(a, b) = [int(x) - 1 for x in input().split()]
	G[a].append((a, b))
	G[b].append((b, a))
(best, index) = (0, 0)
for i in range(n):
	if len(G[i]) > best:
		best = len(G[i])
		index = i
(visited, edges) = ([0] * n, [])
visited[index] = 1
queue = collections.deque(G[index])
while queue:
	vertex = queue.popleft()
	if visited[vertex[1]] == 0:
		visited[vertex[1]] = 1
		edges.append(vertex)
		queue.extend(G[vertex[1]])
for e in edges:
	print(e[0] + 1, e[1] + 1)


(n, m) = list(map(int, input().split()))
from collections import defaultdict, deque
g = defaultdict(set)
for i in range(m):
	(a, b) = list(map(int, input().split()))
	g[a - 1].add(b - 1)
	g[b - 1].add(a - 1)
ma = 0
vis = [0 for i in range(n)]
for i in g:
	if len(g[i]) > ma:
		ma = max(ma, len(g[i]))
		k = i
ans = []
vis[k] = 1
q = deque()
for i in g[k]:
	vis[i] = 1
	ans.append((k, i))
	q.append(i)
while q:
	cur = q.popleft()
	for i in g[cur]:
		if vis[i] == 0:
			q.append(i)
			ans.append((i, cur))
			vis[i] = 1
for (x, y) in ans:
	print(x + 1, y + 1)


from collections import defaultdict, deque
(n, m, d) = map(int, input().split())
g = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
init_set = set(g[1])
if d > len(g[1]):
	print('NO')
	exit()
vis = set()
vis.add(1)
cluster = set()
while init_set:
	node = init_set.pop()
	q = deque()
	q.append(node)
	vis.add(node)
	cluster.add(node)
	while q:
		u = q.popleft()
		for child in g[u]:
			if child not in vis:
				if child in init_set:
					init_set.remove(child)
				vis.add(child)
				q.append(child)
if len(cluster) > d:
	print('NO')
	exit()
q = deque()
vis = set()
vis.add(1)
ans = []
for node in cluster:
	q.append(node)
	vis.add(node)
	ans.append((1, node))
cnt = d - len(cluster)
for remain in g[1]:
	if cnt <= 0:
		break
	if remain not in cluster:
		q.append(remain)
		vis.add(remain)
		ans.append((1, remain))
		cnt -= 1
while q:
	node = q.popleft()
	for child in g[node]:
		if child not in vis:
			vis.add(child)
			q.append(child)
			ans.append((node, child))
print('YES')
for (u, v) in ans:
	print(u, v)


import sys
input = sys.stdin.readline

def solve():
	(n, m) = [int(x) for x in input().split(' ')]
	G = {}
	for i in range(m):
		e = tuple([int(x) for x in input().split(' ')])
		for j in range(2):
			if e[j] in G:
				G[e[j]].append(e[1 - j])
			else:
				G[e[j]] = [e[1 - j]]
	M = 0
	k = -1
	for x in G:
		if len(G[x]) > M:
			M = len(G[x])
			k = x
	q = [k]
	span = []
	visited = {k}
	while q:
		x = q.pop()
		for u in G[x]:
			if u not in visited:
				span.append((x, u))
				visited.add(u)
				q.append(u)
	return span
ans = solve()
for r in ans:
	print(*r)


(n, m, D) = [int(x) for x in input().split(' ')]
G = {}
for u in range(1, n + 1):
	G[u] = set()
for i in range(m):
	(u, v) = [int(x) for x in input().split(' ')]
	G[u].add(v)
	G[v].add(u)
if len(G[1]) < D:
	print('NO')
else:
	visited = [1] + [0] * n
	comp = [0] * (n + 1)
	c_visited = [1] + [0] * n
	a = 0
	for i in G[1]:
		if not visited[i]:
			a += 1
			comp[i] = a
			visited[i] = 1
			q = [i]
			while len(q) > 0:
				u = q.pop(0)
				for v in G[u]:
					if v != 1 and (not visited[v]):
						q.append(v)
						comp[v] = a
						visited[v] = 1
	if a > D:
		print('NO')
	else:
		print('YES')
		d = D
		visited[1] = 2
		queue = []
		n_edges = 0
		for v in G[1]:
			if not c_visited[comp[v]]:
				visited[v] = 2
				d -= 1
				c_visited[comp[v]] = 1
				n_edges += 1
				print(1, v)
				queue.append(v)
		if d:
			for v in G[1]:
				if visited[v] != 2:
					visited[v] = 2
					d -= 1
					print(1, v)
					n_edges += 1
					queue.append(v)
					if not d:
						break
		while len(queue) > 0 and n_edges < n - 1:
			u = queue.pop(0)
			for v in G[u]:
				if visited[v] != 2:
					visited[v] = 2
					queue.append(v)
					n_edges += 1
					print(u, v)


import sys
import math
from collections import defaultdict, deque
import heapq

def find(node, parent):
	while parent[node] != node:
		node = parent[node]
	return node

def union(a, b, child, parent):
	para = find(a, parent)
	parb = find(b, parent)
	ca = child[para]
	cb = child[parb]
	if para != parb:
		if ca > cb:
			parent[parb] = para
			child[para] += child[parb]
		else:
			parent[para] = parb
			child[parb] += child[para]
(n, m, d) = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
parent = [i for i in range(n + 1)]
child = [1 for i in range(n + 1)]
edges = []
for i in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	graph[u].append(v)
	graph[v].append(u)
vis = defaultdict(int)
q = deque()
vis[1] = 1
for j in graph[1]:
	if vis[j] == 0:
		vis[j] = 1
		q.append(j)
		child[j] += 1
		while q:
			cur = q.pop()
			for i in graph[cur]:
				if vis[i] == 0:
					q.append(i)
					if cur != 1 and i != 1:
						union(cur, i, child, parent)
					vis[i] = 1
if len(graph[1]) < d:
	print('NO')
	sys.exit()
cnt = set()
for i in graph[1]:
	cnt.add(find(i, parent))
if len(cnt) > d:
	print('NO')
	sys.exit()
q = deque()
res = 0
ans = []
vis = defaultdict(int)
for i in cnt:
	ans.append([1, i])
	q.append(i)
	vis[i] = 1
	res += 1
rem = d - res
vis[1] = 1
for i in graph[1]:
	if rem > 0 and vis[i] == 0:
		vis[i] = 1
		q.append(i)
		rem -= 1
		ans.append([1, i])
while q:
	cur = q.popleft()
	for j in graph[cur]:
		if vis[j] == 0:
			q.append(j)
			ans.append([cur, j])
			vis[j] = 1
print('YES')
for i in range(n - 1):
	print(ans[i][0], ans[i][1])


import collections as cc
import math as mt
import sys
I = lambda : list(map(int, input().split()))

def find(u):
	while u != parent[u]:
		u = parent[u]
	return u

def union(u, v):
	a = find(u)
	b = find(v)
	if a != b:
		parent[a] = parent[b] = min(a, b)
(n, m, d) = I()
uu = set()
uu.add(1)
parent = [i for i in range(n + 1)]
g = cc.defaultdict(list)
on = []
tf = cc.defaultdict(int)
other = []
for i in range(m):
	(x, y) = sorted(I())
	g[x].append(y)
	g[y].append(x)
	if x != 1 and y != 1:
		other.append([x, y])
		union(x, y)
temp = g[1]
con = [find(i) for i in set(temp)]
if len(set(con)) > d or len(set(temp)) < d:
	print('NO')
	sys.exit()
else:
	print('YES')
	used = cc.defaultdict(int)
	ans = []
	st = cc.deque()
	use = [0] * (n + 1)
	use[1] = 1
	j = 0
	for i in range(len(temp)):
		if not used[find(temp[i])]:
			used[find(temp[i])] = 1
			ans.append([1, temp[i]])
			st.append(temp[i])
			use[temp[i]] = 1
			d -= 1
	for i in range(d):
		while use[temp[j]] == 1:
			j += 1
		ans.append([1, temp[j]])
		st.append(temp[j])
		use[temp[j]] = 1
	while st:
		x = st.popleft()
		use[x] = 1
		for y in g[x]:
			if not use[y]:
				ans.append([x, y])
				st.append(y)
				use[y] = 1
	for i in ans:
		print(*i)


import sys
import collections
(v, e) = map(int, input().strip().split())
graph = collections.defaultdict(list)
degree = [0 for i in range(v)]
(mx, src) = (0, 0)
for i in range(e):
	(a, b) = map(int, input().strip().split())
	degree[a - 1] += 1
	graph[a].append(b)
	if degree[a - 1] > mx:
		mx = degree[a - 1]
		src = a
	degree[b - 1] += 1
	graph[b].append(a)
	if degree[b - 1] > mx:
		mx = degree[b - 1]
		src = b
queue = collections.deque()
queue.append(src)
seen = set()
seen.add(src)
while queue:
	cur = queue.popleft()
	for i in graph[cur]:
		if i in seen:
			continue
		seen.add(i)
		queue.append(i)
		print(str(cur) + ' ' + str(i) + '\r')


import sys
input = sys.stdin.readline
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
edges = []
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
	edges.append([a - 1, b - 1])
root = -1
max_deg = 0
must_edges = []
for i in range(n):
	if max_deg < len(g[i]):
		root = i
		max_deg = len(g[i])
for x in g[root]:
	must_edges.append([root, x])
uf = UnionFind(n)
for (u, v) in must_edges:
	uf.union(u, v)
for (u, v) in edges:
	if not uf.same(u, v):
		uf.union(u, v)
		must_edges.append([u, v])
for (u, v) in must_edges:
	print(u + 1, v + 1)


from collections import deque
import sys
input = sys.stdin.readline

def bfs(s):
	q = deque()
	q.append(s)
	visit = [0] * (n + 1)
	visit[s] = 1
	ans = []
	while q:
		i = q.popleft()
		for j in G[i]:
			if not visit[j]:
				ans.append((i, j))
				q.append(j)
				visit[j] = 1
	return ans
(n, m) = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	G[u].append(v)
	G[v].append(u)
ma = 0
for i in range(1, n + 1):
	if ma < len(G[i]):
		ma = len(G[i])
		s = i
ans = bfs(s)
for (u, v) in ans:
	print(u, v)


(n, m) = list(map(int, input().split()))
a = [list(map(int, input().split())) for i in range(m)]
b = [[] for j in range(n)]
for i in range(m):
	b[a[i][0] - 1].append(a[i][1] - 1)
	b[a[i][1] - 1].append(a[i][0] - 1)
stm = 0
stv = 0
used = [0] * n
for i in range(n):
	if len(b[i]) > stm:
		stm = len(b[i])
		stv = i
ocher = [0] * 1000009
u = 0
k = 1
ocher[0] = stv

def bfs(x):
	nonlocal k
	for i in range(len(b[x])):
		if used[b[x][i]] == 0:
			print(x + 1, b[x][i] + 1)
			used[b[x][i]] = 1
			ocher[k] = b[x][i]
			k += 1
used[stv] = 1
while k - u > 0:
	bfs(ocher[u])
	u += 1


(n, m) = map(int, input().split())
G = {}
v = 0
c = -1
for i in range(m):
	(a, b) = map(int, input().split())
	try:
		G[a].append(b)
		if len(G[a]) > v:
			c = a
			v = len(G[a])
	except:
		G[a] = [b]
		if v < 1:
			c = a
			v = 1
	try:
		G[b].append(a)
		if len(G[b]) > v:
			c = b
			v = len(G[b])
	except:
		G[b] = [a]
		if v < 1:
			c = b
			v = 1
A = {}
for i in G.keys():
	A[i] = -1
q = [c]
A[c] = 1
while len(q) != 0:
	a = q.pop()
	for i in G[a]:
		if A[i] == -1:
			print(a, i)
			q.append(i)
			A[i] = 1


import sys
input = sys.stdin.readline

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

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

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True
MAXN = int(100000.0 + 5)
import math

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

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

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left
from collections import Counter
import heapq
from collections import Counter
from bisect import bisect_right
import heapq
import math

def divisors_seive(n):
	divisors = [10 ** 6 + 6]
	for i in range(1, n + 1):
		for j in range(i, n + 1):
			divisors[j] += 1

def dfs(s, par, vis, rank):
	vis[s] = 1
	global res
	res = 1
	rank[s] = 1
	f = 0
	for i in g[s]:
		f = 1
		if par == i:
			continue
		rank[s] += dfs(i, s)
	return res
import bisect
from collections import deque
(n, m) = map(int, input().split())
vis = [0] * (n + 1)
q = []
g = [[] for i in range(n)]
ind = [0] * n
for i in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
	ind[u - 1] += 1
	ind[v - 1] += 1
node = ind.index(max(ind))
q.append(node)
ans = []
while q:
	s = q.pop()
	vis[s] = 1
	for i in g[s]:
		if vis[i] == 0:
			vis[i] = 1
			q.append(i)
			ans.append([s + 1, i + 1])
for i in ans:
	print(*i)


import sys
from collections import Counter, defaultdict

def i_ints():
	return map(int, sys.stdin.readline().split())
(n, m, D) = i_ints()
E = defaultdict(set)
for i in range(m):
	(u, v) = i_ints()
	E[u].add(v)
	E[v].add(u)

def append_edge(u, v):
	E[v].discard(u)
	t.add(v)
	te.append((u, v))

def complete_tree(u):
	global too_much
	todo = {u}
	while todo:
		u = todo.pop()
		for v in list(E[u]):
			if v not in t:
				if v not in starts:
					append_edge(u, v)
					todo.add(v)
				elif too_much > 0:
					append_edge(u, v)
					todo.add(v)
					too_much -= 1

def print_tree():
	for (u, v) in te:
		print(u, v)
u0 = 1
t = {u0}
te = []
starts = set(E[u0])
too_much = len(starts) - D
if too_much >= 0:
	for v in starts:
		if v not in t:
			append_edge(u0, v)
			complete_tree(v)
if not too_much:
	print('YES')
	print_tree()
else:
	print('NO')


(n, m) = map(int, input().split())
data = []
for i in range(n + 1):
	data.append(set())
maxn = 0
for i in range(m):
	(a, b) = map(int, input().split())
	data[a].add(b)
	data[b].add(a)
	if len(data[a]) > maxn:
		maxn = len(data[a])
		maxv = a
	if len(data[b]) > maxn:
		maxn = len(data[b])
		maxv = b
burned = set()
burned.add(maxv)
current = set()
for c in data[maxv]:
	burned.add(c)
	current.add(c)
	print(maxv, c)
while len(burned) < n:
	newc = set()
	for vertex in current:
		for linked in data[vertex]:
			if linked not in burned:
				burned.add(linked)
				newc.add(linked)
				print(vertex, linked)
	current = newc


(n, m) = map(int, input().split())
ind = [0] * n
adj = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
	ind[u] += 1
	ind[v] += 1
xx = ind.index(max(ind))
vis = [0] * n
st = []
st.append(xx)
vis[xx] = True
while st:
	xx = st[-1]
	st.pop()
	for i in adj[xx]:
		if not vis[i]:
			st.append(i)
			vis[i] = True
			print(i + 1, xx + 1)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
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')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def main():
	er = []
	graph = defaultdict(list)
	(n, m, d) = map(int, input().split())
	vis = [0] * n
	pre = [-1] * n

	def dfs(v, p):
		pre[v] = p
		vis[v] = 1
		for i in graph[v]:
			if vis[i] == 0:
				dfs(i, v)
	for i in range(m):
		(a, b) = map(int, input().split())
		if a == 1:
			er.append(b - 1)
		elif b == 1:
			er.append(a - 1)
		else:
			graph[a - 1].append(b - 1)
			graph[b - 1].append(a - 1)
	for i in range(len(er)):
		if vis[er[i]] == 0:
			dfs(er[i], -1)
	t = 0
	for i in range(len(er)):
		if pre[er[i]] == -1:
			pre[er[i]] = 0
			t += 1
	if t > d:
		print('NO')
		return
	for i in range(len(er)):
		if pre[er[i]] == 0:
			continue
		if t < d:
			pre[er[i]] = 0
			t += 1
		else:
			break
	if t < d:
		print('NO')
		return
	rt = 0
	for i in range(n):
		if pre[i] == -1:
			rt += 1
		if rt >= 2:
			print('NO')
			return
	print('YES')
	for i in range(n):
		if pre[i] != -1:
			print(pre[i] + 1, i + 1)
t = threading.Thread(target=main)
t.start()
t.join()


import sys
input = sys.stdin.readline
(n, m, D) = map(int, input().split())
E = [list(map(int, input().split())) for i in range(m)]
EDGELIST = [[] for i in range(n + 1)]
for (x, y) in E:
	EDGELIST[x].append(y)
	EDGELIST[y].append(x)
Group = [i for i in range(n + 1)]

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		Group[find(y)] = Group[find(x)] = min(find(y), find(x))
ONE = EDGELIST[1]
for (x, y) in E:
	if x == 1 or y == 1:
		continue
	Union(x, y)
ONEU = [find(e) for e in ONE]
if len(set(ONEU)) > D or D > len(ONE):
	print('NO')
	sys.exit()
else:
	print('YES')
USED = set()
ANS = []
from collections import deque
QUE = deque()
check = [0] * (n + 1)
check[1] = 1
for j in range(len(ONE)):
	if find(ONE[j]) in USED:
		continue
	else:
		ANS.append([1, ONE[j]])
		QUE.append(ONE[j])
		USED.add(find(ONE[j]))
		check[ONE[j]] = 1
		D -= 1
j = 0
for i in range(D):
	while check[ONE[j]] == 1:
		j += 1
	ANS.append([1, ONE[j]])
	QUE.append(ONE[j])
	check[ONE[j]] = 1
while QUE:
	x = QUE.popleft()
	check[x] = 1
	for to in EDGELIST[x]:
		if check[to] == 0:
			ANS.append([x, to])
			QUE.append(to)
			check[to] = 1
for (x, y) in ANS:
	print(x, y)


(n, m) = map(int, input().split())
g = []
for i in range(n):
	g.append([])
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u] += [v]
	g[v] += [u]
start = max(range(n), key=lambda i: len(g[i]))
edges = []
vis = [False] * n
q = [start]
vis[start] = True
while q:
	u = q.pop(0)
	for v in g[u]:
		if vis[v]:
			continue
		vis[v] = True
		edges.append((u, v))
		q.append(v)
for (u, v) in edges:
	print(u + 1, v + 1)


from collections import deque

def bfs(node):
	visited = [False for i in range(n + 1)]
	q = deque()
	q.append(node)
	visited[node] = True
	while q:
		node = q.popleft()
		for child in g[node]:
			if visited[child] == False:
				print(node, child)
				q.append(child)
				visited[child] = True
(n, m) = map(int, input().split())
g = {i: [] for i in range(1, n + 1)}
deg = [0 for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
	deg[u] = deg[u] + 1
	deg[v] = deg[v] + 1
m = max(deg)
for i in range(1, n + 1):
	if deg[i] == m:
		index = i
		break
bfs(index)


import math
from collections import defaultdict as dd

def printTree(s):
	q = [s]
	visited[s] = 1
	while q:
		cur = q.pop(-1)
		for i in graph[cur]:
			if visited[i] == 0:
				visited[i] = 1
				print(cur, i)
				q.append(i)
(n, m) = [int(i) for i in input().split()]
graph = dd(list)
visited = [0 for i in range(n + 1)]
for _ in range(m):
	(u, v) = [int(i) for i in input().split()]
	graph[u].append(v)
	graph[v].append(u)
max_deg_node = 0
mx = 0
for i in range(1, n + 1):
	cur = len(graph[i])
	if cur > mx:
		mx = cur
		max_deg_node = i
printTree(max_deg_node)


(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
root = 0
for i in range(n):
	if len(g[i]) > len(g[root]):
		root = i
uf = [-1 for _ in range(n)]

def find(u):
	if uf[u] < 0:
		return u
	else:
		ans = find(uf[u])
		uf[u] = ans
		return ans

def merge(u, v):
	pu = find(u)
	pv = find(v)
	if pu == pv:
		return
	if uf[pu] > uf[pv]:
		(pu, pv) = (pv, pu)
	uf[pu] += uf[pv]
	uf[pv] = pu
ans = []
for v in g[root]:
	merge(root, v)
	ans.append((root + 1, v + 1))
for i in range(n):
	for v in g[i]:
		if find(i) != find(v):
			merge(i, v)
			ans.append((i + 1, v + 1))
print('\n'.join(map(lambda x: '{} {}'.format(x[0], x[1]), ans)))


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	c = dict(Counter(l))
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
rank = [0] * 200005

def find(parent, node):
	if parent[node] == node:
		return node
	parent[node] = find(parent, parent[node])
	return parent[node]

def union(parent, x, y):
	if find(parent, x) == find(parent, y):
		return
	x = find(parent, x)
	y = find(parent, y)
	if rank[x] < rank[y]:
		parent[x] = y
	elif rank[x] > rank[y]:
		parent[y] = x
	else:
		parent[y] = x
		rank[x] += 1

def solve():
	(n, m) = li()
	parent = [i for i in range(n)]
	adj = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = li()
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	for i in range(n):
		adj[i] = [len(adj[i])] + [i] + adj[i]
	adj.sort(reverse=True)
	newadj = [[] for i in range(n)]
	ans = []
	for ii in range(n):
		i = adj[ii][1]
		for j in adj[ii][2:]:
			if find(parent, i) != find(parent, j):
				union(parent, i, j)
				ans.append([i + 1, j + 1])
				newadj[i].append(j)
				newadj[j].append(i)
	for i in ans:
		print(*i)
t = 1
for _ in range(t):
	solve()


from sys import stdin, stdout

def INI():
	return int(stdin.readline())

def INL():
	return [int(_) for _ in stdin.readline().split()]

def INS():
	return stdin.readline()

def MOD():
	return pow(10, 9) + 7

def OPS(ans):
	stdout.write(str(ans) + '\n')

def OPL(ans):
	[stdout.write(str(_) + ' ') for _ in ans]
	stdout.write('\n')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(v):
	V[v] = 0
	for _ in X[v]:
		if V[_] == 1 or (V[_] == 2 and v == m):
			print(v, _)
			yield dfs(_)
	yield
(n, m) = INL()
X = [[] for _ in range(n + 1)]
V = [1 for _ in range(n + 1)]
C = [0 for _ in range(n + 1)]
for _ in range(m):
	(u, v) = INL()
	X[u].append(v)
	X[v].append(u)
	C[u] += 1
	C[v] += 1
m = 1 + C[1:].index(max(C[1:]))
for _ in X[m]:
	V[_] = 2
dfs(m)


(n, m) = list(map(int, input().split()))
d = {i + 1: [] for i in range(n)}
for i in range(m):
	(a, b) = list(map(int, input().split()))
	d[a].append(b)
	d[b].append(a)
maxln = len(d[1])
maxel = 1
for i in d:
	if len(d[i]) > maxln:
		maxel = i
		maxln = len(d[i])
l = [maxel]
k = 0
visit = [0 for i in range(n)]
visit[maxel - 1] = 1
while k < len(l):
	for i in range(len(d[l[k]])):
		if visit[d[l[k]][i] - 1] == 0:
			print(d[l[k]][i], l[k])
			visit[d[l[k]][i] - 1] = 1
			l.append(d[l[k]][i])
	k += 1


import sys
from collections import defaultdict as dd
import heapq
mod = 10 ** 9 + 7

def ri(flag=0):
	if flag == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
(n, m) = ri()
t = dd(list)
r = [0 for i in range(n + 1)]
vis = [0 for i in range(n + 1)]
for i in range(m):
	(u, v) = ri()
	t[u].append(v)
	t[v].append(u)
for i in range(n + 1):
	r[i] = len(t[i])
final = []

def bfs(sor):
	s = [sor]
	vis[sor] = 1
	while s:
		k = s.pop(-1)
		for i in t[k]:
			if vis[i] == 0:
				vis[i] = 1
				s.append(i)
				final.append((k, i))
bfs(r.index(max(r)))
assert len(final) == n - 1
for i in final:
	print(*i)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
deg = [0] * n
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	g[x].append(y)
	g[y].append(x)
	deg[x] += 1
	deg[y] += 1
vis = [False] * n
pos = 0
for i in range(n):
	if deg[pos] < deg[i]:
		pos = i
st = [pos]
vis[pos] = True
ans = []
while len(st):
	x = st[0]
	st.pop(0)
	for i in g[x]:
		if vis[i] == False:
			vis[i] = True
			st.append(i)
			ans.append([i, x])
for i in ans:
	print(i[0] + 1, i[1] + 1)


[n, m, d] = map(int, input().split())
g = {}
for i in range(n):
	g[i + 1] = set()
for i in range(m):
	[v, u] = map(int, input().split())
	g[u].add(v)
	g[v].add(u)
seen = set()
comps = set()
for node in g[1]:
	if node in seen:
		continue
	comps.add(node)
	seen.add(node)
	q = [node]
	while len(q) > 0:
		v = q.pop()
		for to in g[v]:
			if to in seen or to == 1:
				continue
			q.append(to)
			seen.add(to)
if d > len(g[1]) or d < len(comps):
	print('NO')
else:
	print('YES')
	rem = 0
	rem2 = []
	for i in g[1]:
		if len(g[1]) - rem == d:
			break
		if i not in comps:
			rem2.append(i)
			rem += 1
	for i in rem2:
		g[1].discard(i)
	seen.clear()
	q = [1]
	while len(q) > 0:
		v = q.pop()
		discard = []
		for to in g[v]:
			if to in seen or to == 1:
				continue
			q.append(to)
			seen.add(to)
			print(v, ' ', to)


import sys
input = sys.stdin.readline
from collections import deque

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d

	def addEdge(self, x, y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root):
		queue = [root]
		queue = deque(queue)
		vis = [0] * self.n
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					print(element + 1, i + 1)
					queue.append(i)
					vis[i] = 1
					self.parent[i] = element

	def dfs(self, root, ans):
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i] == 0:
					self.parent[i] = element
					stack.append(i)
		while len(stack2) != 0:
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i != self.parent[element]:
					m += ans[i]
			ans[element] = m
		return ans

	def shortestpath(self, source, dest):
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]] != -1:
			path.append(parent[path[-1]])
		return path[::-1]

	def ifcycle(self):
		self.bfs(0)
		queue = [0]
		vis = [0] * n
		queue = deque(queue)
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in graph[element]:
				if vis[i] == 1 and i != parent[element]:
					return True
				if vis[i] == 0:
					queue.append(i)
					vis[i] = 1
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0] * n
		while len(stack) != 0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue
(n, m) = map(int, input().split())
g = Graph(n, False)
for i in range(m):
	(x, y) = map(int, input().split())
	g.addEdge(x - 1, y - 1)
maxx = 0
for i in range(n):
	if len(g.graph[i]) > maxx:
		v = i
		maxx = len(g.graph[i])
g.bfs(v)


class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.rank = [1] * (n + 1)
		self.rank[0] = 0

	def union(self, x, y):
		if not self.same_set(x, y):
			par_x = self.find(x)
			par_y = self.find(y)
			if self.rank[par_x] >= self.rank[par_y]:
				self.rank[par_x] += self.rank[par_y]
				self.rank[par_y] = 0
				self.par[par_y] = par_x
			else:
				self.rank[par_y] += self.rank[par_x]
				self.rank[par_x] = 0
				self.par[par_x] = par_y
			self.find(x)
			self.find(y)

	def find(self, x):
		if self.par[x] == x:
			return x
		self.par[x] = self.find(self.par[x])
		return self.par[x]

	def same_set(self, x, y):
		return self.find(x) == self.find(y)
(n, m) = map(int, input().split())
adj = [[] for i in range(n + 1)]
arestas = []
for i in range(m):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
	arestas.append((a, b))
maior = 1
for i in range(2, n + 1):
	if len(adj[i]) > len(adj[maior]):
		maior = i
uf = UnionFind(n + 1)
for v in adj[maior]:
	uf.union(maior, v)
	print(maior, v)
for (a, b) in arestas:
	if a == maior or b == maior:
		continue
	if not uf.same_set(a, b):
		uf.union(a, b)
		print(a, b)


(n, m) = tuple(map(int, input().split()))
data = []
for i in range(n + 1):
	data.append(set())
maxn = 0
for i in range(m):
	(a, b) = tuple(map(int, input().split()))
	data[a].add(b)
	data[b].add(a)
	if len(data[a]) > maxn:
		maxn = len(data[a])
		maxv = a
	if len(data[b]) > maxn:
		maxn = len(data[b])
		maxv = b
found = {maxv}
current = set()
for c in data[maxv]:
	found.add(c)
	current.add(c)
	print(str(maxv) + ' ' + str(c))
while len(found) < n:
	newc = set()
	for el in current:
		for chi in data[el]:
			if chi not in found:
				found.add(chi)
				newc.add(chi)
				print(str(el), str(chi))
	current = newc


from collections import defaultdict
from collections import deque

def main():
	(n, m) = map(int, input().split())
	edge_dict = defaultdict(list)
	for _ in range(m):
		(u, v) = map(int, input().split())
		edge_dict[u].append(v)
		edge_dict[v].append(u)
	(max_root, max_degree) = (0, 0)
	for i in range(1, n + 1):
		if len(edge_dict[i]) > max_degree:
			(max_root, max_degree) = (i, len(edge_dict[i]))
	(queue, visit) = (deque(), set())
	queue.append(max_root)
	visit.add(max_root)
	ret = []
	while queue:
		u = queue.popleft()
		for v in edge_dict[u]:
			if v not in visit:
				visit.add(v)
				queue.append(v)
				ret.append((u, v))
	for (u, v) in ret:
		print(u, v)

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
countn = [0] * (n + 1)
g = dict()
for i in range(m):
	(u, v) = map(int, input().split())
	countn[u] += 1
	countn[v] += 1
	if u in g:
		g[u].append(v)
	else:
		g[u] = [v]
	if v in g:
		g[v].append(u)
	else:
		g[v] = [u]
cIndex = countn.index(max(countn))
visited = [False] * (n + 1)
qVisit = [cIndex]
visited[cIndex] = True
while len(qVisit) > 0:
	i = qVisit.pop()
	for j in g[i]:
		if not visited[j]:
			print(i, j)
			visited[j] = True
			qVisit.append(j)


import sys
line = sys.stdin.readline().strip().split()
n = int(line[0])
m = int(line[1])
d = [0] * n
x = [[] for i in range(0, n)]
for i in range(0, m):
	line = sys.stdin.readline().strip().split()
	u = int(line[0]) - 1
	v = int(line[1]) - 1
	d[u] = d[u] + 1
	d[v] = d[v] + 1
	x[u].append(v)
	x[v].append(u)
m = max(d)
for i in range(0, n):
	if d[i] == m:
		s = i
L = [s]
d[s] = -1
i = 0
while len(L) != n:
	for v in x[L[i]]:
		if d[v] != -1:
			print(str(L[i] + 1) + ' ' + str(v + 1))
			L.append(v)
			d[v] = -1
	i = i + 1


import sys
from collections import deque
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
MAX = -1
ne = -1
for i in range(n):
	if MAX < len(g[i]):
		MAX = len(g[i])
		ne = i
ans = []
mita = [0] * n
mita[ne] = 1

def dfs(x):
	for i in g[x]:
		if mita[i] == 0:
			ans.append([x + 1, i + 1])
			mita[i] = 1
			que.append(i)
que = deque()
que.append(ne)
while que:
	dfs(que.popleft())
for (i, j) in ans:
	print(i, j)


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
E = [list(map(int, input().split())) for i in range(m)]
cost = [0] * (n + 1)
EDGELIST = [[] for i in range(n + 1)]
for (x, y) in E:
	cost[x] += 1
	cost[y] += 1
	EDGELIST[x].append(y)
	EDGELIST[y].append(x)
x = cost.index(max(cost))
from collections import deque
QUE = deque([x])
check = [0] * (n + 1)
ANS = []
while QUE:
	x = QUE.popleft()
	check[x] = 1
	for to in EDGELIST[x]:
		if check[to] == 0:
			ANS.append([x, to])
			QUE.append(to)
			check[to] = 1
for (x, y) in ANS:
	print(x, y)


(n, m) = map(int, input().split())
a = [0 for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(m):
	(c, d) = map(int, input().split())
	a[c - 1] += 1
	a[d - 1] += 1
	b[c - 1].append(d - 1)
	b[d - 1].append(c - 1)
maxi = 0
for i in range(n):
	if a[maxi] < a[i]:
		maxi = i
used = [False for _ in range(n)]
from collections import deque
q = deque()
ans = []
q.append([-1, maxi])
used[maxi] = True
while len(q) != 0:
	pos = q.popleft()
	if pos[0] != -1:
		ans.append([pos[0] + 1, pos[1] + 1])
	for i in b[pos[1]]:
		if not used[i]:
			q.append([pos[1], i])
			used[i] = True
for i in ans:
	print(*i)


(n, m) = list(map(int, input().split()))
g = [[] for i in range(n + 1)]
ans = set()
for i in range(m):
	(x, y) = list(map(int, input().split()))
	if y > x:
		(x, y) = (y, x)
	g[x].append(y)
	g[y].append(x)
im = 0
mx = 0
used = [False] * (n + 1)
for i in range(1, n + 1):
	if len(g[i]) > mx:
		mx = len(g[i])
		im = i
rip = set()
q = [im]
k = 0
d = [0] * (n + 1)
d[im] = 1
while len(q) > k:
	for v in g[q[k]]:
		if d[v] == 0:
			print(v, q[k])
			d[v] = 1
			q.append(v)
	k += 1


from collections import defaultdict, deque
from sys import stdin
input = stdin.readline
(n, m) = map(int, input().split())
arr = [tuple(map(int, input().split())) for _ in range(m)]
dct = defaultdict(lambda : [])
for (u, v) in arr:
	dct[u].append(v)
	dct[v].append(u)
mx = max(dct.items(), key=lambda t: len(t[1]))[0]
viz = {mx}
st = deque([mx])
es = []
while st:
	r = st.popleft()
	for c in dct[r]:
		if c not in viz:
			st.append(c)
			viz.add(c)
			es.append((r, c))
for e in es:
	print(*e)


from collections import defaultdict
(n, m) = list(map(int, input().split()))
ad = defaultdict(list)
ans = []
for i in range(m):
	(x, y) = map(int, input().split())
	ad[x].append(y)
	ad[y].append(x)

def BFS(s):
	visited = [False] * (n + 1)
	queue = []
	k = 0
	queue.append(s)
	visited[s] = True
	while k < len(queue):
		s = queue[k]
		k += 1
		for i in ad[s]:
			if visited[i] == False:
				queue.append(i)
				ans.append((s, i))
				visited[i] = True
	for i in range(n - 1):
		print(ans[i][0], ans[i][1])
m = 0
s = 1
for i in ad:
	if len(ad[i]) > m:
		m = len(ad[i])
		s = i
BFS(s)


from collections import defaultdict
(n, m) = map(int, input().split())
visited = [0] * (n + 1)
dic = defaultdict(list)
max1 = 0
start = 0
vertices = [0] * (n + 1)
for i in range(m):
	(x, y) = map(int, input().split())
	vertices[x] += 1
	vertices[y] += 1
	dic[x].append(y)
	dic[y].append(x)
length = len(vertices)
for i in range(length):
	if vertices[i] > max1:
		t = (i, vertices[i])
		max1 = vertices[i]
bfs = [t[0]]
visited[t[0]] = 1
pointer = 0
while True:
	if pointer >= len(bfs):
		break
	x = bfs[pointer]
	visited[x] = 1
	for i in dic[x]:
		if visited[i] == 1:
			continue
		visited[i] = 1
		print(x, i)
		bfs.append(i)
	pointer += 1


from collections import deque
(n, m, d) = map(int, input().split())
g = [[] for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)

def bfs(init, c, p=False):
	global color
	q = deque(init)
	while len(q) > 0:
		u = q.popleft()
		for v in g[u]:
			if color[v] < 0:
				if p:
					print(u, v)
				q.append(v)
				color[v] = c
color = [-1 for i in range(n + 1)]
color[1] = 0
c = 0
for x in g[1]:
	if color[x] < 0:
		color[x] = c
		bfs([x], c)
		c += 1
if len(g[1]) < d or d < c:
	print('NO')
else:
	is_kid = [False for x in g[1]]
	kids = []
	picked = [False for i in range(c)]
	for i in range(len(g[1])):
		x = g[1][i]
		if not picked[color[x]]:
			is_kid[i] = True
			kids.append(x)
			picked[color[x]] = True
	extra = d - c
	for i in range(len(g[1])):
		x = g[1][i]
		if extra == 0:
			break
		if not is_kid[i]:
			is_kid[i] = True
			kids.append(x)
			extra -= 1
	color = [-1 for i in range(n + 1)]
	color[1] = 0
	print('YES')
	for x in kids:
		print(1, x)
		color[x] = 0
	bfs(kids, 0, True)


from collections import deque
(n, m) = map(int, input().split())
e = []
a = [[] for i in range(n)]
for i in range(m):
	(fr, to) = map(int, input().split())
	e.append((fr, to))
	a[fr - 1].append(to - 1)
	a[to - 1].append(fr - 1)
root = 0
maxPow = 0
for i in range(n):
	if len(a[i]) > maxPow:
		root = i
		maxPow = len(a[i])
visited = set()
d = deque()
d.append(root)
visited.add(root)
while len(d) != 0:
	cur = d.popleft()
	for adj in a[cur]:
		if adj not in visited:
			print(cur + 1, adj + 1)
			visited.add(adj)
			d.append(adj)


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

def main():

	def union(u, v):
		(p, q) = (find(u), find(v))
		if p == q:
			return
		if rank[p] < rank[q]:
			(p, q) = (q, p)
		if rank[p] == rank[q]:
			rank[p] += 1
		parent[q] = p

	def find(u):
		p = parent[u]
		if p == u:
			return u
		root = find(p)
		parent[u] = root
		return root
	(n, m, D) = map(int, input().split())
	E = []
	E0 = []
	E0rmn = []
	MSTE = []
	parent = list(range(n))
	rank = [0] * n
	for _ in range(m):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		if u == 0 or v == 0:
			E0.append((u, v))
		else:
			E.append((u, v))
	if len(E0) < D:
		print('NO')
		return
	for (u, v) in E:
		if find(u) != find(v):
			union(u, v)
			MSTE.append((u, v))
	k = 0
	for (u, v) in E0:
		if find(u) != find(v):
			union(u, v)
			MSTE.append((u, v))
			k += 1
		else:
			E0rmn.append((u, v))
	if D < k:
		print('NO')
		return
	while k < D:
		e = E0rmn.pop()
		MSTE.append(e)
		k += 1
	parent = list(range(n))
	rank = [0] * n
	out = ['YES']
	for (u, v) in reversed(MSTE):
		if find(u) != find(v):
			union(u, v)
			out.append(str(u + 1) + ' ' + str(v + 1))
	print('\n'.join(out))
main()


from collections import defaultdict
(n, m) = map(int, input().split())
d = defaultdict(list)
contador = defaultdict(int)
for i in range(m):
	(a, b) = map(int, input().split())
	contador[a] += 1
	contador[b] += 1
	d[a].append(b)
	d[b].append(a)
maxi = max(contador.values())
maxi_vertice = [v for v in d.keys() if contador[v] == maxi][0]
ans = []
veri = [0] * (n + 1)
veri[maxi_vertice] = 1
count = 0
q = [maxi_vertice]
while count < n - 1:
	x = q.pop()
	for v in d[x]:
		if veri[v]:
			continue
		else:
			ans.append((x, v))
			veri[v] = 1
			count += 1
			q.append(v)
for i in range(n - 1):
	print(*ans[i])


from collections import defaultdict, deque
(n, m) = map(int, input().split())
freq = [0 for _ in range(n + 1)]
adj = defaultdict(list)
for _ in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
	freq[u] += 1
	freq[v] += 1
maxDegNode = freq.index(max(freq))
vis = set()

def bfs(src, res):
	q = deque()
	q.append(src)
	vis.add(src)
	while q:
		curr = q.popleft()
		for child in adj[curr]:
			if child not in vis:
				q.append(child)
				res.append([curr, child])
				vis.add(child)
	return res
res = bfs(maxDegNode, [])
for (u, v) in res:
	print(u, v)


(n, m) = map(int, input().split())
tn = n + 1
edges = [[] for i in range(tn)]
for i in range(m):
	(a, b) = map(int, input().split())
	edges[a].append(b)
	edges[b].append(a)
(max_node, max_degree) = (0, 0)
for i in range(1, tn):
	if len(edges[i]) > max_degree:
		max_degree = len(edges[i])
		max_node = i
candidates = [max_node]
st_edges = []
covered = set([max_node])

def process_candidate(candidate):
	for neb in edges[candidate]:
		if neb not in covered:
			candidates.append(neb)
			st_edges.append((candidate, neb))
			covered.add(neb)
i = 0
while len(covered) < n:
	candidate = candidates[i]
	process_candidate(candidate)
	i += 1
for ste in st_edges:
	print('%s %s' % ste)


import collections

def do():
	graph = collections.defaultdict(list)
	(nodes, edges) = map(int, input().split(' '))
	ind = [0] * (nodes + 1)
	for _ in range(edges):
		(x, y) = map(int, input().split(' '))
		graph[x].append(y)
		graph[y].append(x)
		ind[x] += 1
		ind[y] += 1
	root = 1
	mi = ind[1]
	for i in range(1, nodes + 1):
		if ind[i] > mi:
			mi = ind[i]
			root = i
	seen = [0] * (nodes + 1)
	seen[root] = 1
	res = set()
	q = collections.deque()
	for nei in graph[root]:
		seen[nei] = 1
		res.add((root, nei))
		q.append(nei)
	while q:
		cur = q.popleft()
		for nei in graph[cur]:
			if not seen[nei]:
				seen[nei] = 1
				res.add((cur, nei))
				q.append(nei)
	for (x, y) in list(res):
		print(str(x) + ' ' + str(y))
	return 0
do()


from __future__ import print_function
from collections import *
from sys import stdin
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, m) = gil()
adj = [[] for _ in range(n + 1)]
root = 1
for _ in range(m):
	(x, y) = gil()
	adj[x].append(y)
	adj[y].append(x)
	if len(adj[root]) < max(len(adj[x]), len(adj[y])):
		root = max(x, y, key=lambda x: len(adj[x]))
edg = []
vis = [0] * (n + 1)
st = [root]
while st:
	p = st.pop()
	vis[p] = 1
	for c in adj[p]:
		if vis[c]:
			continue
		edg.append(str(p) + ' ' + str(c))
		vis[c] = 1
		st.append(c)
print('\n'.join(edg))


(n, m) = map(int, input().split())
edges = [tuple(map(int, input().split())) for i in range(m)]
g = [[] for i in range(n + 1)]

class UnionFind:
	__slots__ = ['id']

	def __init__(self, n):
		self.id = [-1] * n

	def root(self, x):
		if self.id[x] < 0:
			return x
		else:
			self.id[x] = self.root(self.id[x])
			return self.id[x]

	def find(self, x, y):
		return self.root(x) == self.root(y)

	def union(self, x, y):
		(s1, s2) = (self.root(x), self.root(y))
		if s1 != s2:
			if self.id[s1] <= self.id[s2]:
				self.id[s1] += self.id[s2]
				self.id[s2] = s1
			else:
				self.id[s2] += self.id[s1]
				self.id[s1] = s2
			return True
		return False
uf = UnionFind(n + 1)
for i in range(m):
	(s, t) = edges[i]
	g[s].append(t)
	g[t].append(s)
hi = 0
for i in range(n + 1):
	if hi < len(g[i]):
		hi = len(g[i])
		a = i
for s in g[a]:
	uf.union(a, s)
	print(a, s)
for (s, t) in edges:
	if not uf.find(s, t):
		uf.union(s, t)
		print(s, t)


(n, m) = [int(x) for x in input().split(' ')]
G = {}
for i in range(m):
	(u, v) = [int(x) for x in input().split(' ')]
	try:
		G[u].append(v)
	except:
		G[u] = [v]
	try:
		G[v].append(u)
	except:
		G[v] = [u]
l = sorted(G, key=lambda k: len(G[k]), reverse=True)
visited = [True] + [False] * n
queue = [l[0]]
visited[l[0]] = True
n_visit = 1
while len(queue) > 0 and n_visit < n:
	u = queue.pop(0)
	for v in G[u]:
		if not visited[v]:
			visited[v] = True
			n_visit += 1
			print(u, v)
			queue.append(v)


import sys
from collections import defaultdict as dd
import heapq
mod = 10 ** 9 + 7

def ri(flag=0):
	if flag == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
(n, m, d) = ri()
t = dd(list)
r = [0 for i in range(n + 1)]
vis = [0 for i in range(n + 1)]
for i in range(m):
	(u, v) = ri()
	t[u].append(v)
	t[v].append(u)
for i in range(n + 1):
	r[i] = len(t[i])
final = []

def bfs(sor):
	s = [sor]
	vis[sor] = 1
	while s:
		k = s.pop(-1)
		for i in t[k]:
			if vis[i] == 0:
				vis[i] = 1
				s.append(i)

def bfs2(sor):
	s = [sor]
	vis[sor] = 1
	while s:
		k = s.pop(-1)
		for i in t[k]:
			if vis[i] == 0:
				vis[i] = 1
				s.append(i)
				final.append((k, i))
now = []
for i in t[1]:
	now.append(i)
lk = 0
go = dd(int)
vis[1] = 1
for i in range(len(t[1])):
	if vis[t[1][i]] == 0:
		bfs(t[1][i])
		go[t[1][i]] = 1
		lk += 1
if lk <= d:
	temp = t[1][:]
	t[1] = []
	for i in go:
		t[1].append(i)
		t[i].append(1)
		d -= 1
	for i in temp:
		if go[i] == 1:
			pass
		elif d != 0:
			t[1].append(i)
			t[i].append(1)
			d -= 1
	if d != 0:
		print('NO')
	else:
		vis = [0 for i in range(n + 1)]
		bfs2(1)
		if sum(vis) == n:
			print('YES')
			for i in final:
				print(*i)
		else:
			print('NO')
else:
	print('NO')


from collections import *

def ans(graph, start, path=[]):
	q = [start]
	mark[start - 1] = 1
	ptr = 0
	while ptr < len(q):
		v = q[ptr]
		for jj in graph[v]:
			if not mark[jj - 1]:
				print(v, jj)
				mark[jj - 1] = 1
				q.append(jj)
		ptr += 1
(n, m) = map(int, input().split())
maxn = int(200000.0 + 10)
G = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	G[u].append(v)
	G[v].append(u)
nextnode = 1
for i in range(1, n + 1):
	if len(G[i]) > len(G[nextnode]):
		nextnode = i
mark = [0] * n
ans(G, nextnode)


from collections import defaultdict
(n, m) = map(int, input().split())
cnt = defaultdict(int)
d = defaultdict(list)
for i in range(m):
	(a, b) = map(int, input().split())
	cnt[a] += 1
	cnt[b] += 1
	d[a].append(b)
	d[b].append(a)
mx = max(cnt.values())
mx_vertice = [v for v in d.keys() if cnt[v] == mx][0]
ans = []
check = [0] * (n + 1)
check[mx_vertice] = 1
count = 0
q = [mx_vertice]
while count < n - 1:
	x = q.pop()
	for v in d[x]:
		if check[v]:
			continue
		else:
			ans.append((x, v))
			check[v] = 1
			count += 1
			q.append(v)
for i in range(n - 1):
	print(*ans[i])


import sys
input = sys.stdin.readline

class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [1] * n

	def root(self, x):
		p = x
		while not self.par[p] < 0:
			p = self.par[p]
		while x != p:
			tmp = x
			x = self.par[x]
			self.par[tmp] = p
		return p

	def unite(self, x, y):
		(rx, ry) = (self.root(x), self.root(y))
		if rx == ry:
			return False
		if self.rank[rx] < self.rank[ry]:
			(rx, ry) = (ry, rx)
		self.par[rx] += self.par[ry]
		self.par[ry] = rx
		if self.rank[rx] == self.rank[ry]:
			self.rank[rx] += 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def count(self, x):
		return -self.par[self.root(x)]
(n, m) = map(int, input().split())
d = [0] * n
adj_list = [[] for _ in range(n)]
edges = []
ans = []
for _ in range(m):
	(v, u) = map(int, input().split())
	d[v - 1] += 1
	d[u - 1] += 1
	adj_list[v - 1].append(u - 1)
	adj_list[u - 1].append(v - 1)
	edges.append((u - 1, v - 1))
uf = Unionfind(n)
max_d = max(d)
for i in range(n):
	if d[i] == max_d:
		for j in adj_list[i]:
			uf.unite(i, j)
			ans.append((i, j))
		break
for (s, t) in edges:
	if not uf.is_same(s, t):
		uf.unite(s, t)
		ans.append((s, t))
for (s, t) in ans:
	print(s + 1, t + 1)


arr = input()
(N, M) = [int(x) for x in arr.split(' ')]
edge_list = [[] for _ in range(N + 1)]
degree = [0] * (N + 1)
for i in range(M):
	s = input()
	(u, v) = [int(x) for x in s.split(' ')]
	edge_list[u].append(v)
	edge_list[v].append(u)
	degree[u] += 1
	degree[v] += 1
visited = [0] * (N + 1)
maxi = 0
node = 0
for i in range(1, N + 1):
	if degree[i] > maxi:
		maxi = degree[i]
		node = i
dfs = [node]
visited[node] = 1
while dfs:
	p = dfs.pop()
	for v in edge_list[p]:
		if visited[v] == 0:
			dfs.append(v)
			visited[v] = 1
			print(p, v)


import sys
from collections import deque
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
(n, m, d) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
ne = 0
ans = []
mita = [0] * n
mita[ne] = -1

def dfs(x, y):
	for i in g[x]:
		if mita[i] == 0:
			ans.append([x + 1, i + 1])
			mita[i] = y
			que.append([i, y])
for i in g[ne]:
	if mita[i] != 0:
		continue
	mita[i] = i
	que = deque()
	que.append([i, i])
	while que:
		(x, y) = que.popleft()
		dfs(x, y)
syo = len(set(mita)) - 1
if syo > d or len(g[ne]) < d:
	print('NO')
	exit()
print('YES')
use = set()
ki = set()
for i in g[ne]:
	if mita[i] in ki:
		continue
	else:
		ki.add(mita[i])
		use.add(i)
for i in g[ne]:
	if len(use) == d:
		break
	if i not in use:
		use.add(i)
g[ne] = list(use)
ans = []
mita = [0] * n
mita[ne] = 1

def dfs(x):
	for i in g[x]:
		if mita[i] == 0:
			ans.append([x + 1, i + 1])
			mita[i] = 1
			que.append(i)
que = deque()
que.append(ne)
while que:
	dfs(que.popleft())
for (i, j) in ans:
	print(i, j)


(n, m) = map(int, input().split())
edges = [[] for _ in range(n + 1)]
newEdge = [[] for _ in range(n + 1)]
done = {}
start = 0
node = 1
for i in range(m):
	(a, b) = map(int, input().split())
	edges[a].append(b)
	edges[b].append(a)
	if len(edges[a]) > start:
		start = len(edges[a])
		node = a
	if len(edges[b]) > start:
		start = len(edges[b])
		node = b
run = [node]
while len(run) > 0:
	temp = []
	next = run.pop()
	done[str(next)] = 1
	for v in edges[next]:
		if str(v) not in done:
			done[str(v)] = 1
			print(next, v)
			temp.append(v)
	run += temp