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: introductory

Starter code:

Solutions:
import sys
input = sys.stdin.readline

n,m,D=list(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")
    return
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
        
#print(ANS)
for x,y in ANS:
    print(x,y)


    
    
    


'''input
7 10 2
7 1
1 3
5 2
6 1
6 5
3 7
5 7
1 2
5 1
1 4
'''
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)
				#final.append((k,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
		else:
			if 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)
		#print(vis,t)
		if sum(vis)==n:
			print("YES")
			for i in final:
				print(*i)
		else:
			print("NO")
else:
	print("NO")



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

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]:
		# print(k,adj[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])

n, m, d = list(map(int, input().split()))

g = [[] for _ in range(n + 1)]

haveOne = [False] * (n + 1)

for i in range(m):
	u, v = list(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:
		# bfs
		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)


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




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




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


'''input
7 10 2
7 1
1 3
5 2
6 1
6 5
3 7
5 7
1 2
5 1
1 4
'''
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)
				#final.append((k,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
		else:
			if 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)
		#print(vis,t)
		if sum(vis)==n:
			print("YES")
			for i in final:
				print(*i)
		else:
			print("NO")
else:
	print("NO")

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[u].discard(v)
    E[v].discard(u)
    t.add(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)
                else:
                    if 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 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[u].discard(v)
    E[v].discard(u)
#    t.add(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)
                else:
                    if 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
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 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")
        return
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)

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
        else:
            if 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()

        
        
        



    


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):
	#print(a,'a',b,'b')
	para=find(a,parent)
	parb=find(b,parent)
	#print(para,'para')
	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)
	#edges.append([u,v])
vis=defaultdict(int)
q=deque()

vis[1]=1
for j in graph[1]:
	if vis[j]==0:
		vis[j]=1
		q.append(j)
		#print(j,'j')
		child[j]+=1
		#print(child[j],'child')
		while q:
			cur=q.pop()
			#print(cur,'cur')
			for i in graph[cur]:
				if vis[i]==0:
					q.append(i)
					if cur!=1 and i!=1:
						#print(cur,'cur',i,'i')
						union(cur,i,child,parent)
					vis[i]=1
if len(graph[1]) < d:
	print("NO")
	return
#print(graph[1],'one')
#print(parent,'parent')
#print(child,'child')
cnt=set()
for i in graph[1]:
	cnt.add(find(i,parent))
#print(cnt,'cnt')
if len(cnt)>d:
	print("NO")
	return
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")
	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")
    return
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
        
#print(ANS)
for x,y in ANS:
    print(x,y)

# ---------------------------iye ha aam zindegi---------------------------------------------
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

# ------------------------------warmup----------------------------
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")


# -------------------game starts now----------------------------------------------------import math
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):
        """
        Side effect!!! Changes node. Node should have exactly one child
        """
        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


# -----------------------------------------------binary seacrh tree---------------------------------------
class SegmentTree1:
    def __init__(self, data, default=2**51, func=lambda a, b: a & b):
        """initialize the segment tree with data"""
        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)


# -------------------game starts now----------------------------------------------------import math
class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b: a + b):
        """initialize the segment tree with data"""
        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)


# -------------------------------iye ha chutiya zindegi-------------------------------------
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)  # To make sure already calculated n^-1
        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


# --------------------------------------iye ha combinations ka zindegi---------------------------------
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


# --------------------------------------iye ha power ka zindegi---------------------------------
def sort_list(list1, list2):
    zipped_pairs = zip(list2, list1)

    z = [x for _, x in sorted(zipped_pairs)]

    return z


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


# --------------------------------------------------binary----------------------------------------
def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left) / 2)

        # Check if middle element is
        # less than or equal to key
        if (arr[mid] < key):
            count = mid + 1
            left = mid + 1

        # If key is smaller, ignore right half
        else:
            right = mid - 1

    return count


# --------------------------------------------------binary----------------------------------------
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

    # Stores the index of the left most element
    # from the array which is greater than k
    leftGreater = n

    # Finds number of elements greater than k
    while (l <= r):
        m = int(l + (r - l) / 2)
        if (arr[m] >= k):
            leftGreater = m
            r = m - 1

        # If mid element is less than
        # or equal to k update l
        else:
            l = m + 1

    # Return the count of elements
    # greater than k
    return (n - leftGreater)


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