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 degree of the first vertex (vertex with label $1$ on it) is equal to $D$ (or say that there are no such spanning trees). Recall that the degree of a vertex is the number of edges incident to it.


-----Input-----

The first line contains three integers $n$, $m$ and $D$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2}), 1 \le D < n$) — the number of vertices, the number of edges and required degree of the first vertex, 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-----

If there is no spanning tree satisfying the condition from the problem statement, print "NO" in the first line.

Otherwise print "YES" in the first line and then print $n-1$ lines describing the edges of a spanning tree such that the degree of the first vertex (vertex with label $1$ on it) is equal to $D$. 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
4 5 1
1 2
1 3
1 4
2 3
3 4

Output
YES
2 1
2 3
3 4

Input
4 5 3
1 2
1 3
1 4
2 3
3 4

Output
YES
1 2
1 3
4 1

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

Output
NO



-----Note-----

The picture corresponding to the first and second examples: [Image]

The picture corresponding to the third example: [Image]

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Greedy algorithms

Spanning trees
Skill types: Greedy algorithms

Starter code:

Solutions:
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)


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')
	return
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
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)


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')
	return
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)))


(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)


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()


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):
	nonlocal 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():
	nonlocal v, l1, l2, adj, d, ans, l3, c
	(n, m, d) = list(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) = list(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 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)


(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
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')


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])


[n, m, d] = list(map(int, input().split()))
g = {}
for i in range(n):
	g[i + 1] = set()
for i in range(m):
	[v, u] = list(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 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))
			return
		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))
			return
		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))
			return
		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
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):
	nonlocal 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')


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')

def graph_undirected():
	(n, e, d) = [int(x) for x in input().split()]
	graph = {}
	for i in range(e):
		(vertex, neighbour) = [int(x) for x in input().split()]
		if vertex in graph:
			graph[vertex].append(neighbour)
		else:
			graph[vertex] = [neighbour]
		if neighbour in graph:
			graph[neighbour].append(vertex)
		else:
			graph[neighbour] = [vertex]
	return (graph, n, d)
from collections import deque

def bfs(graph, currnode):
	visited = [False for x in range(n + 1)]
	stack = deque()
	parent = [0 for x in range(n + 1)]
	stack.append(currnode)
	while stack:
		currnode = stack.popleft()
		if visited[currnode] == False:
			visited[currnode] = True
		for neigbour in graph[currnode]:
			if visited[neigbour] == False:
				visited[neigbour] = True
				parent[neigbour] = currnode
				stack.append(neigbour)
	return parent

def bfs1(graph, currnode, visited):
	stack = deque()
	stack.append(currnode)
	while stack:
		currnode = stack.popleft()
		if visited[currnode] == False:
			visited[currnode] = True
		for neigbour in graph[currnode]:
			if visited[neigbour] == False:
				visited[neigbour] = True
				stack.append(neigbour)
	return
(graph, n, d) = graph_undirected()

def solve():
	if len(graph[1]) < d:
		print('NO')
		return
	visited = [False for x in range(n + 1)]
	visited[1] = True
	mustchoose = set()
	for node in graph[1]:
		if visited[node] == False:
			mustchoose.add(node)
			bfs1(graph, node, visited)
	if len(mustchoose) > d:
		print('NO')
		return
	garr = []
	for i in mustchoose:
		garr.append(i)
	for node in graph[1]:
		if len(garr) == d:
			break
		if node not in mustchoose:
			garr.append(node)
	graph[1] = garr
	parent = bfs(graph, 1)
	print('YES')
	for i in range(2, len(parent)):
		sys.stdout.write(str(parent[i]) + ' ' + str(i) + '\n')
solve()


[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))


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')
	return
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')
		return
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])


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)


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

def get_root(s):
	v = []
	while not s == root[s]:
		v.append(s)
		s = root[s]
	for i in v:
		root[i] = s
	return s

def unite(s, t):
	root_s = get_root(s)
	root_t = get_root(t)
	if not root_s == root_t:
		if rank[s] == rank[t]:
			root[root_t] = root_s
			rank[root_s] += 1
			size[root_s] += size[root_t]
		elif rank[s] > rank[t]:
			root[root_t] = root_s
			size[root_s] += size[root_t]
		else:
			root[root_s] = root_t
			size[root_t] += size[root_s]

def same(s, t):
	if get_root(s) == get_root(t):
		return True
	else:
		return False

def bfs(s):
	q = deque()
	q.append(s)
	anss = []
	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 anss
(n, m, d) = map(int, input().split())
G = [[] for _ in range(n + 1)]
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
u1 = []
for _ in range(m):
	(u, v) = map(int, input().split())
	if u ^ 1 and v ^ 1:
		unite(u, v)
		G[u].append(v)
		G[v].append(u)
	else:
		u1.append(u ^ v ^ 1)
s = set()
r = defaultdict(lambda : -1)
for i in u1:
	ri = get_root(i)
	s.add(ri)
	r[ri] = i
ans = 'YES' if len(s) <= d and len(u1) >= d else 'NO'
print(ans)
if ans == 'YES':
	visit = [0] * (n + 1)
	visit[1] = 1
	st = set()
	for i in r:
		st.add(r[i])
	for i in u1:
		if len(st) == d:
			break
		st.add(i)
	for i in st:
		visit[i] = 1
	ans = []
	for i in st:
		ans.append((1, i))
		for (u, v) in bfs(i):
			ans.append((u, v))
	for (u, v) in ans:
		print(u, v)