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

Starter code:

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

# -*- coding: utf-8 -*-
# @Time    : 2019/3/7 23:52
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : F1. Spanning Tree with Maximum Degree.py

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])
    # print(max_root, max_degree)

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

from collections import defaultdict
n,m=list(map(int,input().split()))
ad=defaultdict(list)
ans=[]
for i in range(m):
    x,y=list(map(int,input().split()))
    ad[x].append(y)
    ad[y].append(x)
def BFS(s): 
  
        visited = [False] * (n+1)
  
        # Create a queue for BFS 
        queue = []
        k=0
  
        # Mark the source node as  
        # visited and enqueue it 
        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)

    


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 = 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
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))
#print(x)

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
        
#print(ANS)
for x,y in ANS:
    print(x,y)


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


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 = 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


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

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)

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




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)
#print(g)

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




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)
#print(g)

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


n,m=list(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=list(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
# for l in mp:
# 	print (l)
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=list(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=list(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
vis=[0]*(n+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
vis[s]=1
# for l in mp:
# 	print (l)

while(i<len(stk)):
	k=stk[i][1]
	if vis[k]==0:
		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
		vis[k]=1
	i+=1
for i in range(len(stk)):
	print(*stk[i])


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



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


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