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 choose at most $\lfloor\frac{n}{2}\rfloor$ vertices in this graph so each unchosen vertex is adjacent (in other words, connected by an edge) to at least one of chosen vertices.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.

You will be given multiple independent queries to answer.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^5$) — the number of queries.

Then $t$ queries follow.

The first line of each query 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 the number of 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 self-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. It is guaranteed that the given graph is connected.

It is guaranteed that $\sum m \le 2 \cdot 10^5$ over all queries.


-----Output-----

For each query print two lines.

In the first line print $k$ ($1 \le \lfloor\frac{n}{2}\rfloor$) — the number of chosen vertices.

In the second line print $k$ distinct integers $c_1, c_2, \dots, c_k$ in any order, where $c_i$ is the index of the $i$-th chosen vertex.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.


-----Example-----
Input
2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
6 8
2 5
5 4
4 3
4 1
1 3
2 3
2 6
5 6

Output
2
1 3
3
4 3 6



-----Note-----

In the first query any vertex or any pair of vertices will suffice.

 [Image] 

Note that you don't have to minimize the number of chosen vertices. In the second query two vertices can be enough (vertices $2$ and $4$) but three is also ok.

 [Image]

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Shortest paths

Tree algorithms

Spanning trees

Starter code:

Solutions:
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	E = [[] for aa in range(N)]
	for __ in range(M):
		(a, b) = list(map(int, input().split()))
		E[a - 1].append(b - 1)
		E[b - 1].append(a - 1)
	D = [-1] * N
	D[0] = 0
	d = 0
	post = [0]
	EVEN = [1]
	ODD = []
	while post:
		d += 1
		pre = post
		post = []
		for i in pre:
			for e in E[i]:
				if D[e] < 0:
					D[e] = d
					post.append(e)
					if d % 2:
						ODD.append(e + 1)
					else:
						EVEN.append(e + 1)
	if len(ODD) < len(EVEN):
		print(len(ODD))
		print(*ODD)
	else:
		print(len(EVEN))
		print(*EVEN)


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

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


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


def jiashen(new_tree):
	global g
	global k
	js = []
	for i in new_tree:
		for j in gra[i]:
			if fil[j]:
				fil[j] = 0
				js.append(j)
				g += 1
				if k:
					d2.append(j)
				else:
					d1.append(j)
	k = False if k else True
	return js
t = int(input())
zong = []
for _ in range(t):
	(n, m) = map(int, input().split())
	gra = [[] for i in range(n)]
	d1 = [0]
	d2 = []
	fil = [1 for i in range(n)]
	fil[0] = 0
	for i in range(m):
		(a, b) = map(int, input().split())
		gra[a - 1].append(b - 1)
		gra[b - 1].append(a - 1)
	new_tree = [0]
	k = True
	g = 1
	while g < n:
		new_tree = jiashen(new_tree)
	le = len(d1)
	if le <= n // 2:
		zong.append(str(le) + '\n' + ' '.join([str(x + 1) for x in d1]))
	else:
		zong.append(str(n - le) + '\n' + ' '.join([str(x + 1) for x in d2]))
print('\n'.join(zong))


import sys
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(nodes, src):
	from collections import deque
	N = len(nodes)
	que = deque([(src, 0)])
	dist = [INF] * N
	dist[src] = 0
	while que:
		(u, c) = que.popleft()
		for v in nodes[u]:
			if dist[v] != INF:
				continue
			dist[v] = c + 1
			que.append((v, c + 1))
	return dist
ans = []
for _ in range(INT()):
	(N, M) = MAP()
	nodes = [[] for i in range(N)]
	for _ in range(M):
		(a, b) = MAP()
		a -= 1
		b -= 1
		nodes[a].append(b)
		nodes[b].append(a)
	res = bfs(nodes, 0)
	ans1 = []
	ans2 = []
	for (u, c) in enumerate(res):
		if c % 2 == 0:
			ans1.append(str(u + 1))
		else:
			ans2.append(str(u + 1))
	if len(ans1) <= len(ans2):
		ans.append(str(len(ans1)))
		ans.append(' '.join(ans1))
	else:
		ans.append(str(len(ans2)))
		ans.append(' '.join(ans2))
print('\n'.join(ans))


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


kk = lambda : map(int, input().split())
k2 = lambda : map(lambda x: int(x) - 1, input().split())
ll = lambda : list(kk())
(n, m) = kk()
neighs = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = k2()
	neighs[u].append(v)
	neighs[v].append(u)
m = v = 0
for (i, ls) in enumerate(neighs):
	if len(ls) > m:
		(m, v) = (len(ls), i)
seen = {v}
nex = [v]
while nex:
	newn = []
	for no in nex:
		for nei in neighs[no]:
			if nei not in seen:
				seen.add(nei)
				print(nei + 1, no + 1)
				newn.append(nei)
	nex = newn


from sys import stdin, stdout
from collections import deque
Input = []

def Out(x):
	stdout.write(str(x) + ' ')

def In():
	return stdin.readline().strip()

def inputGrab():
	for line in stdin:
		Input.extend(map(str, line.strip().split()))
inputIDX = 0

def hasNext():
	global inputIDX
	return inputIDX < len(Input)

def nextInt():
	global inputIDX
	inputIDX += 1
	return int(Input[inputIDX - 1])

def nextString():
	global inputIDX
	inputIDX += 1
	return Input[inputIDX - 1]
d = []
G = []

def bfs(u):
	global d
	global G
	eve = 1
	odd = 0
	q = deque()
	q.append(u)
	d[u] = 0
	while len(q) > 0:
		u = q.pop()
		for v in G[u]:
			if d[v] == -1:
				d[v] = d[u] + 1
				q.append(v)
				if d[v] & 1:
					odd += 1
				else:
					eve += 1
	return (eve, odd)

def main():
	global d
	global G
	t = nextInt()
	for __ in range(t):
		V = nextInt()
		E = nextInt()
		d = [-1 for i in range(V + 9)]
		G = [[] for i in range(V + 9)]
		for i in range(E):
			u = nextInt()
			v = nextInt()
			G[u].append(v)
			G[v].append(u)
		(eve, odd) = bfs(1)
		if odd < eve:
			print(odd)
			for i in range(1, V + 1):
				if d[i] & 1 == 1:
					Out(i)
		else:
			print(eve)
			for i in range(1, V + 1):
				if d[i] & 1 == 0:
					Out(i)
		stdout.write('\n')
inputGrab()
main()


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	gr = [set() for i in range(n)]
	for j in range(m):
		(x, y) = map(int, input().split())
		gr[x - 1].add(y - 1)
		gr[y - 1].add(x - 1)
	s = list(gr[0])
	tr = {}
	tr[0] = 0
	pim = []
	v = [False for i in range(n)]
	for c in s:
		tr[c] = 1
		v[c] = True
	v[0] = True
	pa = 1
	ppa = [1]
	imp = 0
	while s:
		x = s.pop()
		if tr[x] % 2 == 0:
			pa += 1
			ppa.append(x + 1)
		else:
			imp += 1
			pim.append(x + 1)
		for j in gr[x]:
			if v[j]:
				continue
			v[j] = True
			tr[j] = tr[x] + 1
			s.append(j)
	if pa < imp:
		print(pa)
		print(*ppa)
	else:
		print(imp)
		print(*pim)


from collections import deque
import sys
t = int(input())
lns = sys.stdin.readlines()
i = 0
result = []
for _ in range(t):
	(n, m) = map(int, lns[i].split())
	i += 1
	g = [[] for _ in range(n)]
	for _ in range(m):
		(v, u) = map(int, lns[i].split())
		i += 1
		g[v - 1].append(u - 1)
		g[u - 1].append(v - 1)
	q = deque()
	vis = [False] * n
	lvl = [-1] * n
	lvl[0] = 0
	vis[0] = True
	q.append(0)
	while len(q) > 0:
		v = q.popleft()
		for u in g[v]:
			if not vis[u]:
				vis[u] = True
				lvl[u] = lvl[v] + 1
				q.append(u)
	odd = [str(i + 1) for i in range(n) if lvl[i] % 2 == 1]
	even = [str(i + 1) for i in range(n) if lvl[i] % 2 == 0]
	res = odd if len(odd) < len(even) else even
	result.append(str(len(res)))
	result.append(' '.join(res))
print('\n'.join(result))


from collections import deque

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


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


import sys
input = sys.stdin.readline
RI = lambda : [int(x) for x in input().strip().split()]
rw = lambda : input().strip().split()
from collections import defaultdict as df

def dfs(a, n):
	depth = [0] * n
	depth[a] = 0
	x = 1
	stack = [a]
	vis[a] = 1
	l = [0, 0]
	l[0] += 1
	while len(stack) != 0:
		p = stack.pop()
		for i in adj[p]:
			if vis[i] == 1:
				continue
			vis[i] = 1
			stack.append(i)
			depth[i] = depth[p] ^ 1
			l[depth[i]] += 1
		x = (x + 1) % 2
	s = n // 2
	if l[0] <= s:
		print(l[0])
		for i in range(n):
			if depth[i] == 0:
				print(i + 1, end=' ')
	else:
		print(l[1])
		for i in range(n):
			if depth[i] == 1:
				print(i + 1, end=' ')
	print('')
t = int(input())
for _ in range(t):
	(n, m) = RI()
	adj = [[] for i in range(n)]
	vis = [0] * n
	for i in range(m):
		(a, b) = RI()
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	dfs(0, n)


import sys
from collections import deque
for case in range(int(input())):
	(n, m) = map(int, sys.stdin.readline().split())
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = map(int, sys.stdin.readline().split())
		g[x].append(y)
		g[y].append(x)
	col = [-1] * (n + 1)
	col[1] = 1
	Q = deque()
	Q.append(1)
	ans = [[] for i in range(2)]
	ans[1].append(1)
	while Q:
		From = Q.popleft()
		for To in g[From]:
			if col[To] == -1:
				if col[From] == 1:
					col[To] = 2
				else:
					col[To] = 1
				ans[col[To] % 2].append(To)
				Q.append(To)
	if len(ans[0]) < len(ans[1]):
		print(len(ans[0]))
		print(*ans[0])
	else:
		print(len(ans[1]))
		print(*ans[1])


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

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

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


class Item:

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

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


from collections import defaultdict, deque
import sys

def input():
	return sys.stdin.readline().rstrip()
INF = 1 << 128

def slv():
	(n, m) = map(int, input().split())
	g = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	dist = [INF] * n
	stack = deque([0])
	dist[0] = 0
	while stack:
		p = stack.popleft()
		for adjp in g[p]:
			if dist[adjp] == INF:
				dist[adjp] = dist[p] + 1
				stack.append(adjp)
	(even, odd) = (0, 0)
	for i in range(n):
		if dist[i] % 2 == 0:
			even += 1
		else:
			odd += 1
	if even <= odd:
		ans = []
		for i in range(n):
			if dist[i] % 2 == 0:
				ans.append(i + 1)
		print(len(ans))
		print(*ans)
		return
	else:
		ans = []
		for i in range(n):
			if dist[i] % 2 != 0:
				ans.append(i + 1)
		print(len(ans))
		print(*ans)
	return

def main():
	t = int(input())
	for i in range(t):
		slv()
	return
main()


from collections import deque
import sys
for _ in range(int(sys.stdin.readline())):
	(n, m) = list(map(int, sys.stdin.readline().split()))
	g = [[] for _ in range(n + 1)]
	for _ in range(m):
		(a, b) = list(map(int, sys.stdin.readline().split()))
		g[a].append(b)
		g[b].append(a)
	k = [[], [1]]
	color = [-1] * (n + 1)
	m = deque([1])
	color[1] = 1
	while m:
		u = m.popleft()
		for v in g[u]:
			if color[v] == -1:
				color[v] = 1 - color[u]
				k[color[v]].append(v)
				m.append(v)
	if len(k[0]) <= n // 2:
		print(len(k[0]))
		print(*k[0])
	else:
		print(len(k[1]))
		print(*k[1])


from collections import defaultdict, deque
(n, m) = map(int, input().split())
g = defaultdict(list)
counter = [0] * (n + 1)
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
	counter[a] += 1
	counter[b] += 1
source = counter.index(max(counter))
visited = [False] * (n + 1)
visited[source] = True
q = deque([source])
ans = []
while q:
	first = q.popleft()
	for i in g[first]:
		if not visited[i]:
			visited[i] = True
			q.append(i)
			ans.append((i, first))
for i in ans:
	print(*i)


import sys
input = sys.stdin.buffer.readline

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		g = [[] for _ in range(n)]
		for i in range(m):
			(v, u) = map(int, input().split())
			(v, u) = (v - 1, u - 1)
			g[u].append(v)
			g[v].append(u)
		s = []
		visit = [-1] * n
		c = [-1] * n
		s.append(0)
		visit[0] = 0
		c[0] = 1
		while s:
			v = s.pop()
			for u in g[v]:
				if visit[u] == -1:
					visit[u] = 0
					c[u] = 1 - c[v]
					s.append(u)
		Z = []
		NZ = []
		for i in range(n):
			if c[i] == 0:
				Z.append(i + 1)
			else:
				NZ.append(i + 1)
		if len(Z) <= n // 2:
			print(len(Z))
			print(*Z)
		else:
			print(len(NZ))
			print(*NZ)
main()


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


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


def findpar(p):
	if par[p] == p:
		return p
	else:
		ret = findpar(par[p])
		par[p] = ret
		return par[p]

def union(x, y):
	par[findpar(y)] = findpar(x)
	return
(n, m) = map(int, input().split())
par = []
for i in range(n + 4):
	par.append(i)
deg = []
for i in range(n + 4):
	deg.append(0)
edges = []
for i in range(n + 2):
	edges.append([])
for i in range(m):
	(x, y) = map(int, input().split())
	deg[x] += 1
	deg[y] += 1
	edges[x].append(y)
	edges[y].append(x)
curr = root = 0
for i in range(1, n + 2):
	if deg[i] >= curr:
		curr = deg[i]
		root = i
ans = []
queue = []
visit = []
for i in range(n + 3):
	visit.append(0)
queue.append(root)
visit[root] = 1
front = 0
back = 1
while front < back:
	curr = queue[front]
	front += 1
	for to in edges[curr]:
		if visit[to] == 0:
			visit[to] = 1
			ans.append((curr, to))
			queue.append(to)
			back += 1
for Edge in ans:
	print(str(Edge[0]) + ' ' + str(Edge[1]))


import sys
input = sys.stdin.buffer.readline
from collections import deque
sys.setrecursionlimit(100000)

class Graph(object):

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

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

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

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

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

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

	def pdfs(self, root, vis, color):
		for i in self.graph[root]:
			if not vis[i]:
				vis[i] = 1
				self.parent[i] = root
				if color[root]:
					color[i] = 0
					l1.append(i + 1)
				else:
					color[i] = 1
					l2.append(i + 1)
				self.pdfs(i, vis, color)

	def dfss(self, root):
		vis = [0] * self.n
		color = [-1] * self.n
		color[root] = 0
		stack = [root]
		while len(stack) != 0:
			e = stack.pop()
			if vis[e]:
				continue
			if color[e] == -1:
				if color[self.parent[e]]:
					color[e] = 0
					l1.append(e + 1)
				else:
					color[e] = 1
					l2.append(e + 1)
			vis[e] = 1
			for i in self.graph[e]:
				if not vis[i]:
					stack.append(i)
					self.parent[i] = e
		return
test = int(input())
for nt in range(test):
	(n, m) = map(int, input().split())
	g = Graph(n, False)
	for i in range(m):
		(x, y) = map(int, input().split())
		g.addEdge(x, y)
	(l1, l2) = ([1], [])
	g.dfss(0)
	if len(l1) + len(l2) != n:
		print(l1, l2)
		print(1 / 0)
	if len(l2) <= n // 2:
		print(len(l2))
		print(*sorted(l2))
	elif len(l1) <= n // 2:
		print(len(l1))
		print(*sorted(l1))
	else:
		print(1 / 0)


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

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

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


from sys import stdin, stdout
input = stdin.readline

def dfs(start):
	global n, g
	vis = [0 for i in range(n + 1)]
	dis = [0 for i in range(n + 1)]
	stack = []
	stack.append((start, 0))
	while len(stack):
		s = stack.pop()
		node = s[0]
		par = s[1]
		if not vis[node]:
			vis[node] = 1
			dis[node] = dis[par] ^ 1
		for i in g[node]:
			if not vis[i]:
				stack.append((i, node))
	for i in range(1, n + 1):
		if dis[i]:
			odds.append(i)
		else:
			evens.append(i)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		g[a].append(b)
		g[b].append(a)
	evens = []
	odds = []
	dfs(1)
	if len(evens) <= n // 2:
		print(len(evens))
		print(*evens)
	else:
		print(len(odds))
		print(*odds)


import sys
input = sys.stdin.buffer.readline

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

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


from sys import stdin, stdout
import sys
from _collections import defaultdict, deque

def bfs(node):
	q = deque()
	q.append(node)
	visited[node] = True
	while q:
		el = q.popleft()
		for j in adj[el]:
			if not visited[j]:
				q.append(j)
				visited[j] = True
				stdout.write(str(el) + ' ' + str(j) + '\n')
(n, m) = map(int, stdin.readline().split())
adj = defaultdict(list)
for i in range(m):
	(u, v) = map(int, stdin.readline().split())
	adj[u].append(v)
	adj[v].append(u)
visited = [False] * (n + 1)
(maxdeg, maxnode) = (0, -1)
for i in range(1, n + 1):
	if len(adj[i]) > maxdeg:
		maxdeg = len(adj[i])
		maxnode = i
bfs(maxnode)


from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def prime_factors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

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

def fibonacci_modP(n, MOD):
	if n < 2:
		return 1
	return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n, p):
	if p <= n:
		return 0
	res = p - 1
	for i in range(n + 1, p):
		res = res * cached_fn(InverseEuler, i, p) % p
	return res

def binary(n, digits=20):
	b = bin(n)[2:]
	b = '0' * (digits - len(b)) + b
	return b

def is_prime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

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

def warm_up_fac(MOD):
	global factorial_modP, fac_warm_up
	if fac_warm_up:
		return
	factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
	for i in range(2, fac_warm_up_size):
		factorial_modP[i] = factorial_modP[i - 1] * i % MOD
	fac_warm_up = True

def InverseEuler(n, MOD):
	return pow(n, MOD - 2, MOD)

def nCr(n, r, MOD):
	global fac_warm_up, factorial_modP
	if not fac_warm_up:
		warm_up_fac(MOD)
		fac_warm_up = True
	return factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD

def test_print(*args):
	if testingMode:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def display_2D_list(li):
	for i in li:
		print(i)

def prefix_sum(li):
	sm = 0
	res = []
	for i in li:
		sm += i
		res.append(sm)
	return res

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result

def ncr(n, r):
	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def binary_search(i, li):
	fn = lambda x: li[x] - x // i
	x = -1
	b = len(li)
	while b >= 1:
		while b + x < len(li) and fn(b + x) > 0:
			x += b
		b = b // 2
	return x
TestCases = True
fac_warm_up_size = 10 ** 5 + 100
optimise_for_recursion = False

def main():
	(n, m) = get_tuple()
	adj = [[] for _ in range(n)]
	visited = [False for _ in range(n)]
	for _ in range(m):
		(x, y) = get_tuple()
		adj[x - 1].append(y - 1)
		adj[y - 1].append(x - 1)
	queue = [0]
	mk = 1
	res = [[], []]
	visited[0] = True
	while len(queue) > 0:
		mk = mk ^ 1
		temp_q = []
		for vertex in queue:
			res[mk].append(vertex + 1)
			for j in adj[vertex]:
				if not visited[j]:
					temp_q.append(j)
					visited[j] = True
		queue = temp_q
	print(min(len(res[0]), len(res[1])))
	display_list(res[0]) if len(res[0]) < len(res[1]) else display_list(res[1])
if TestCases:
	for i in range(get_int()):
		main()
else:
	main() if not optimise_for_recursion else threading.Thread(target=main).start()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
for _ in range(ii()):
	(n, m) = kk()
	edgelist = [set() for i in range(n)]
	used = [False] * n
	for _ in range(m):
		(u, v) = kk()
		(u, v) = (u - 1, v - 1)
		edgelist[u].add(v)
		edgelist[v].add(u)
	sets = [set(), set()]
	index = 0
	ls = {0}
	done = 0
	while done < n:
		ls2 = set()
		for l in ls:
			if not used[l]:
				used[l] = True
				sets[index].add(l)
				ls2 |= edgelist[l]
				done += 1
		ls = ls2
		index ^= 1
	s = sets[0] if len(sets[0]) < len(sets[1]) else sets[1]
	print(len(s))
	print(' '.join([str(v + 1) for v in s]))


import sys

class Main:

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

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

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

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

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


import sys
input = sys.stdin.buffer.readline

def bfs():
	visited = [0 for i in range(n + 1)]
	stack = [1]
	child = 0
	while stack:
		q = stack.pop()
		if visited[q] == 1:
			continue
		visited[q] = 1
		for child in graph[q]:
			if visited[child] == 0:
				counted[child] = (counted[q] + 1) % 2
				stack.append(child)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	counted = [0 for i in range(n + 1)]
	bfs()
	odd = 0
	even = 0
	for i in range(1, n + 1):
		if counted[i] == 0:
			even += 1
		else:
			odd += 1
	if even < odd:
		print(even)
		for i in range(1, n + 1):
			if counted[i] == 0:
				print(i, end=' ')
	else:
		print(odd)
		for i in range(1, n + 1):
			if counted[i] == 1:
				print(i, end=' ')


from collections import deque

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

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


import sys
input = sys.stdin.buffer.readline

def process(G):
	g = {}
	for (a, b) in G:
		if a not in g:
			g[a] = set([])
		if b not in g:
			g[b] = set([])
		g[a].add(b)
		g[b].add(a)
	start = [1]
	seen = {1: 0}
	counts = [[1], []]
	n = len(g)
	while len(seen) < n:
		next_s = []
		for x in start:
			for y in g[x]:
				if y not in seen:
					seen[y] = 1 - seen[x]
					counts[seen[y]].append(y)
					next_s.append(y)
					g[y].remove(x)
		start = next_s
	if len(counts[0]) < len(counts[1]):
		return counts[0]
	else:
		return counts[1]
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	G = []
	for j in range(m):
		(a, b) = [int(x) for x in input().split()]
		G.append([a, b])
	answer = process(G)
	sys.stdout.write(str(len(answer)) + '\n')
	sys.stdout.write(' '.join(map(str, answer)) + '\n')


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

def main():

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

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


import sys
from collections import Counter, defaultdict

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

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

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

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


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


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


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
kk = lambda : map(int, input().split())
k2 = lambda : map(lambda x: int(x) - 1, input().split())
ll = lambda : list(kk())
(n, m) = kk()
neighs = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = k2()
	neighs[u].append(v)
	neighs[v].append(u)
m = v = 0
for (i, ls) in enumerate(neighs):
	if len(ls) > m:
		(m, v) = (len(ls), i)
seen = [False] * n
nex = [v]
seen[v] = True
ls = [None] * (n - 1)
i = 0
while nex:
	newn = []
	for no in nex:
		for nei in neighs[no]:
			if not seen[nei]:
				seen[nei] = True
				ls[i] = str(nei + 1) + ' ' + str(no + 1)
				i += 1
				newn.append(nei)
	nex = newn
print('\n'.join(ls))


from collections import deque
import sys
input = sys.stdin.readline
T = int(input())
for r in range(T):
	(n, m) = list(map(int, input().split()))
	ADL = {i: set() for i in range(1, n + 1)}
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		ADL[x].add(y)
		ADL[y].add(x)
	to_visit = [True] * len(ADL)
	current = deque()
	current.append(1)
	parity = [False] * n
	to_visit[0] = False
	while current:
		vertex = current.popleft()
		for i in ADL[vertex]:
			if to_visit[i - 1]:
				parity[i - 1] = not parity[vertex - 1]
				current.append(i)
				to_visit[i - 1] = False
	if sum(parity) <= n // 2:
		s = set([i + 1 for i in range(n) if parity[i]])
	else:
		s = set([i + 1 for i in range(n) if not parity[i]])
	print(len(s))
	print(*s)


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

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

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

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


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().strip().split()]
	graph = {}
	for i in range(m):
		(u, v) = [int(x) for x in input().strip().split()]
		if u not in graph:
			graph[u] = []
		if v not in graph:
			graph[v] = []
		graph[u].append(v)
		graph[v].append(u)
	visited = {}
	flag = {}
	for i in range(1, n + 1):
		visited[i] = 0
		flag[i] = 0
	visited[1] = 1
	s = [1]
	sl = 1
	j = 0
	while sl > j:
		i = s[j]
		if flag[i] == 1:
			j += 1
		else:
			if i in graph:
				if visited[i] == -1:
					temp = 1
				elif visited[i] == 1:
					temp = -1
				flag[i] = 1
				for adj in graph[i]:
					if flag[adj] == 0:
						visited[adj] = temp
						s.append(adj)
						sl += 1
			j += 1
	count1 = 0
	count2 = 0
	for v in visited:
		if visited[v] == 1:
			count1 += 1
		else:
			count2 += 1
	if count1 < count2:
		print(count1)
		temp = 1
	else:
		print(count2)
		temp = -1
	for v in visited:
		if visited[v] == temp:
			print(v, end=' ')
	print()


import sys

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


class Union:

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

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

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


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

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


I = lambda : list(map(int, input().split()))
import sys
input = sys.stdin.readline
import collections as cc
for tc in range(int(input())):
	(n, m) = I()
	g = cc.defaultdict(list)
	deg = [0] * (n + 1)
	for i in range(m):
		(x, y) = I()
		g[x].append(y)
		g[y].append(x)
		deg[x] += 1
		deg[y] += 1
	ar = []
	for i in range(1, n + 1):
		ar.append([i, deg[i]])
	ar.sort(key=lambda i: i[1], reverse=True)
	ans = []
	visi = [0] * (n + 1)
	comp = []
	for i in ar:
		(x, y) = i
		if not visi[x]:
			ans.append(x)
			visi[x] = 1
			for j in g[x]:
				if visi[j] == 0:
					comp.append(j)
				visi[j] = 1
	if len(ans) > n // 2:
		print(len(comp))
		print(*comp)
	else:
		print(len(ans))
		print(*ans)


import sys
input = sys.stdin.readline
from collections import deque
Q = int(input())
for q in range(Q):
	(n, m) = list(map(int, input().split()))
	E = [list(map(int, input().split())) for i in range(m)]
	ELIST = [[] for i in range(n + 1)]
	for (a, b) in E:
		ELIST[a].append(b)
		ELIST[b].append(a)
	check = [0] * (n + 1)
	ANS = []
	Q = deque([1])
	E2 = [[] for i in range(n + 1)]
	while Q:
		x = Q.pop()
		check[x] = 1
		for to in ELIST[x]:
			if check[to] == 0:
				E2[x].append(to)
				E2[to].append(x)
				check[to] = 1
				Q.append(to)
	ELIST = E2
	check = [0] * (n + 1)
	QUE = deque([])
	QUE.append([1, 0])
	while QUE:
		(x, point) = QUE.pop()
		if point == 0:
			if check[x] == 1:
				continue
			check[x] = 1
			ANS.append(x)
			for to in ELIST[x]:
				if check[to] == 0:
					check[to] = 1
					QUE.appendleft([to, 1])
		else:
			for to in ELIST[x]:
				if check[to] == 0:
					QUE.appendleft([to, 0])
	if len(ANS) <= n // 2:
		print(len(ANS))
		print(*ANS)
		continue
	check = [0] * (n + 1)
	ANS = []
	QUE = deque([])
	QUE.append([ELIST[1][0], 0])
	while QUE:
		(x, point) = QUE.pop()
		if point == 0:
			if check[x] == 1:
				continue
			check[x] = 1
			ANS.append(x)
			for to in ELIST[x]:
				if check[to] == 0:
					check[to] = 1
					QUE.appendleft([to, 1])
		else:
			for to in ELIST[x]:
				if check[to] == 0:
					QUE.appendleft([to, 0])
	print(len(ANS))
	print(*ANS)


from collections import deque

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


from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 7)

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

def lin():
	return list(map(int, stdin.readline().split()))

def BFS(s, adj):
	level = {s: 0}
	parent = {s: None}
	lv = 1
	u = [s]
	while u:
		nextu = []
		for i in u:
			for v in adj[i]:
				if v not in parent:
					parent[v] = i
					level[v] = lv
					nextu.append(v)
		lv += 1
		u = nextu.copy()
	return level

def main():
	t = iin()
	while t:
		t -= 1
		(n, m) = lin()
		adj = [[] for i in range(n)]
		for _ in range(m):
			(i, j) = lin()
			i -= 1
			j -= 1
			adj[i].append(j)
			adj[j].append(i)
		sl = BFS(0, adj)
		g1 = []
		g2 = []
		for i in range(n):
			if sl[i] % 2:
				g1.append(i + 1)
			else:
				g2.append(i + 1)
		(l1, l2) = (len(g1), len(g2))
		ans = []
		if l1 > l2:
			ans = g2[:] + g1[:n // 2 - l2]
		else:
			ans = g1[:] + g2[:n // 2 - l1]
		print(n // 2)
		print(*ans[:n // 2])
main()


from typing import List
par = []
rnk = []

def find(x: int) -> int:
	global par
	if par[x] != x:
		par[x] = find(par[x])
	return par[x]

def Union(u: int, v: int) -> None:
	global par, rnk
	x = find(u)
	y = find(v)
	if x == y:
		return
	if rnk[x] > rnk[y]:
		par[y] = x
	elif rnk[x] < rnk[y]:
		par[x] = y
	else:
		par[x] = y
		rnk[y] += 1

def findSpanningTree(deg: List[int], n: int, m: int, g: List[List[int]]) -> None:
	global rnk, par
	par = [i for i in range(n + 1)]
	rnk = [0] * (n + 1)
	max = 1
	for i in range(2, n + 1):
		if deg[i] > deg[max]:
			max = i
	for v in g[max]:
		print('{} {}'.format(max, v))
		Union(max, v)
	for u in range(1, n + 1):
		for v in g[u]:
			x = find(u)
			y = find(v)
			if x == y:
				continue
			Union(x, y)
			print('{} {}'.format(u, v))
(n, m) = [int(i) for i in input().split()]
g = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
	(a, b) = [int(i) for i in input().split()]
	g[a].append(b)
	g[b].append(a)
	deg[a] += 1
	deg[b] += 1
findSpanningTree(deg, n, m, g)


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


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

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


kk = lambda : map(int, input().split())
k2 = lambda : map(lambda x: int(x) - 1, input().split())
ll = lambda : list(kk())
(n, m) = kk()
neighs = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = k2()
	neighs[u].append(v)
	neighs[v].append(u)
m = v = 0
for (i, ls) in enumerate(neighs):
	if len(ls) > m:
		(m, v) = (len(ls), i)
seen = set(neighs[v])
seen.add(v)
dsuroot = [i for i in range(n)]
dsurank = [0 for i in range(n)]
edges = []

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

def union(x, y):
	(rx, ry) = (find(x), find(y))
	if rx == ry:
		return -1
	if dsurank[rx] < dsurank[y]:
		(rx, ry) = (ry, rx)
	dsuroot[ry] = rx
	if dsurank[rx] == dsurank[ry]:
		dsurank[rx] += 1
	edges.append((x, y))
	return 1
for no in neighs[v]:
	union(v, no)
for i in range(n):
	for nei in neighs[i]:
		if nei < i:
			union(i, nei)
print()
print('\n'.join([' '.join([str(x + 1) for x in e]) for e in edges]))


from sys import stdin

def main():
	(n, m) = map(int, stdin.readline().split())
	G = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, stdin.readline().split())
		G[u - 1].append(v - 1)
		G[v - 1].append(u - 1)
	visited = [0 for _ in range(n)]
	t = [-1, -1]
	for i in range(n):
		if len(G[i]) > t[0]:
			t[0] = len(G[i])
			t[1] = i
	visited[t[1]] = 1
	stack = list()
	stack.append(t[1])
	while len(stack) != 0:
		u = stack.pop()
		for v in G[u]:
			if not visited[v]:
				print(u + 1, v + 1)
				visited[v] = 1
				stack.append(v)
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')
from collections import deque

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


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


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


import sys
from collections import defaultdict, deque

def bfs(start, tree):
	vis = defaultdict(int)
	mark = []
	q = deque()
	q.append(start)
	vis[start] = 1
	connect = set()
	while q:
		a = q.popleft()
		if vis[a] == 1:
			mark.append(a)
		for i in tree[a]:
			if vis[i] == 0 and vis[a] == 1:
				vis[i] = 2
				q.append(i)
				continue
			elif vis[i] == 0 and vis[a] == 2:
				vis[i] = 1
				q.append(i)
			elif vis[a] == 1 and vis[i] == 1:
				vis[i] = 2
	return mark
t = int(sys.stdin.readline())
for _ in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	tree = defaultdict(list)
	for i in range(m):
		(u, v) = map(int, sys.stdin.readline().split())
		tree[u].append(v)
		tree[v].append(u)
		last = u
	for i in tree:
		a = bfs(i, tree)
		if len(a) <= n // 2:
			print(len(a))
			print(*a)
			break


from sys import stdin, stdout, exit
from collections import deque
q = int(input())
for it in range(q):
	(n, m) = map(int, stdin.readline().split())
	adj = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, stdin.readline().split())
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	dists = [-1] * n
	todo = deque([0])
	dists[0] = 0
	while todo:
		top = todo.popleft()
		for nbr in adj[top]:
			if dists[nbr] == -1:
				dists[nbr] = dists[top] + 1
				todo.append(nbr)
	e = []
	o = []
	for v in range(n):
		if dists[v] % 2 == 0:
			e.append(v + 1)
		else:
			o.append(v + 1)
	if len(e) <= n // 2:
		ans = e
	else:
		ans = o
	stdout.write(str(len(ans)) + '\n')
	stdout.write(' '.join(map(str, ans)) + '\n')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque

def main():
	for j in range(int(input())):
		(n, m) = map(int, input().split())
		graph = [[] for s in range(n)]
		root = 0
		for s in range(m):
			(u, v) = map(int, input().split())
			u -= 1
			v -= 1
			graph[u].append(v)
			graph[v].append(u)
			root = u
		ans = set([root + 1])
		cv = 1
		par = 0
		queue = deque([root])
		vis = set([root])
		while len(queue) > 0:
			v0 = queue.popleft()
			for s in graph[v0]:
				if not s in vis:
					queue.append(s)
					vis.add(s)
			if par % 2 == 0:
				ans.add(v0 + 1)
			cv -= 1
			if cv == 0:
				par += 1
				cv = len(queue)
		if len(ans) <= n // 2:
			print(len(ans))
			print(*list(ans))
		else:
			new = []
			for s in range(n):
				if not s + 1 in ans:
					new.append(s + 1)
			print(len(new))
			print(*new)
main()


import sys
input = sys.stdin.readline

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


class UnionFind:

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

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

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

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


from sys import stdin
(t,) = map(int, stdin.readline().split())
for _ in range(t):
	(n, m) = map(int, stdin.readline().split())
	graph = dict()
	for _ in range(m):
		(a, b) = map(int, stdin.readline().split())
		try:
			graph[a].append(b)
		except:
			graph[a] = [b]
		try:
			graph[b].append(a)
		except:
			graph[b] = [a]
	sortedGraph = sorted(graph.items(), key=lambda x: len(x[1]))
	nodes = []
	resp = []
	visited = [False] * (n + 1)
	while sortedGraph:
		(u, _) = sortedGraph.pop()
		if not visited[u]:
			visited[u] = True
			resp.append(u)
			for v in graph[u]:
				if not visited[v]:
					visited[v] = True
					nodes.append(v)
	if len(resp) > n // 2:
		print(len(nodes))
		print(*nodes)
	else:
		print(len(resp))
		print(*resp)


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


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

def bfs(s):
	q = deque()
	q.append(s)
	dist = [-1] * (n + 1)
	dist[s] = 0
	c = 0
	while q:
		i = q.popleft()
		di = dist[i]
		c += di % 2
		for j in G[i]:
			if dist[j] == -1:
				dist[j] = di + 1
				q.append(j)
	x = 1 if c <= n - c else 0
	ans = []
	for i in range(1, n + 1):
		if dist[i] % 2 == x:
			ans.append(i)
	return ans
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	G = [[] for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		G[u].append(v)
		G[v].append(u)
	ans = bfs(1)
	print(len(ans))
	print(*ans)


from sys import stdin

def mr():
	return [int(x) for x in stdin.readline().split()]
t = int(input())
for i in range(t):
	(n, m) = mr()
	d = {i: set() for i in range(1, n + 1)}
	for i in range(m):
		(a, b) = mr()
		d[a].add(b)
		d[b].add(a)
	one_set = {1}
	other_set = set()
	stack = [(1, 0)]
	while len(stack) > 0:
		(v, tp) = stack.pop()
		for w in d[v]:
			if w in one_set or w in other_set:
				continue
			stack.append((w, 1 - tp))
			if tp == 1:
				one_set.add(w)
			else:
				other_set.add(w)
	res = one_set if len(one_set) < len(other_set) else other_set
	print(len(res))
	for x in res:
		print(x, end=' ')
	print()


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


import sys
from collections import deque
for _ in range(int(input())):
	(n, m) = map(int, sys.stdin.readline().split())
	a = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = map(int, sys.stdin.readline().split())
		a[x].append(y)
		a[y].append(x)
	col = [-1] * (n + 1)
	col[1] = 1
	d = deque([1])
	vis = [0] * (n + 1)
	ans = [[], [1]]
	while d:
		p = d.popleft()
		for i in a[p]:
			if col[i] == -1:
				col[i] = 1 - col[p]
				ans[1 - col[p]].append(i)
				d.append(i)
	if len(ans[0]) <= n // 2:
		print(len(ans[0]))
		print(*ans[0])
	else:
		print(len(ans[1]))
		print(*ans[1])


import sys
input = sys.stdin.readline

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	g = [[] for i 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)
	c = [-1] * n
	q = [0]
	c[0] = 0
	while q:
		ver = q.pop()
		for to in g[ver]:
			if c[to] == -1:
				q.append(to)
				c[to] = c[ver] ^ 1
			else:
				continue
	c1 = sum(c)
	c0 = n - c1
	ans = []
	if c1 <= c0:
		for i in range(n):
			if c[i]:
				ans.append(i + 1)
	else:
		for i in range(n):
			if c[i] == 0:
				ans.append(i + 1)
	print(len(ans))
	print(*ans)


import sys
input = sys.stdin.readline
Q = int(input())
Query = []
for _ in range(Q):
	(N, M) = map(int, input().split())
	graph = [[] for _ in range(N)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		graph[a - 1].append(b - 1)
		graph[b - 1].append(a - 1)
	Query.append((N, M, graph))
for (N, M, graph) in Query:
	q = [0]
	checked = [False] * N
	checked[0] = True
	dis = [[1], []]
	d = 0
	while q:
		qq = []
		d += 1
		for p in q:
			for np in graph[p]:
				if not checked[np]:
					checked[np] = True
					qq.append(np)
					dis[d % 2].append(np + 1)
		q = qq
	if len(dis[0]) > len(dis[1]):
		print(len(dis[1]))
		for a in dis[1]:
			print(a, end=' ')
		print()
	else:
		print(len(dis[0]))
		for a in dis[0]:
			print(a, end=' ')
		print()


from collections import deque

def bfs(grafo, no, n):
	vis = [False] * n
	resul = []
	q = deque()
	vis[no] = True
	q.append(no)
	while q:
		top = q.popleft()
		for viz in grafo[top]:
			if not vis[viz]:
				vis[viz] = True
				q.append(viz)
				print('{} {}'.format(top + 1, viz + 1))
(n, m) = map(int, input().split())
grafo = [[] for _ in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	grafo[u].append(v)
	grafo[v].append(u)
max_ = 0
no = 0
for i in range(n):
	if len(grafo[i]) > max_:
		max_ = len(grafo[i])
		max_i = i * 1
bfs(grafo, max_i, n)


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

def bfs():
	q = deque([0])
	dist = [-1] * n
	dist[0] = 0
	while q:
		v = q.popleft()
		for nv in G[v]:
			if dist[nv] == -1:
				dist[nv] = dist[v] + 1
				q.append(nv)
	return dist
for _ in range(int(input())):
	(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)
	dist = bfs()
	e = 0
	for i in range(n):
		if dist[i] % 2 == 0:
			e += 1
	if e < n - e:
		print(e)
		ans = [i + 1 for i in range(n) if dist[i] % 2 == 0]
		print(*ans)
	else:
		print(n - e)
		ans = [i + 1 for i in range(n) if dist[i] % 2 == 1]
		print(*ans)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, m) = I()
g = [[] * n for i in range(n)]
for i in range(m):
	(x, y) = I()
	x -= 1
	y -= 1
	g[x].append(y)
	g[y].append(x)
ans = 0
for i in range(n):
	if len(g[ans]) < len(g[i]):
		ans = i
st = [ans]
an = set()
visi = [0] * n
visi[ans] = 1
while st:
	x = st.pop(0)
	for y in g[x]:
		if not visi[y]:
			st.append(y)
			visi[y] = 1
			an.add((x, y))
for i in an:
	print(i[0] + 1, i[1] + 1)


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


import sys

def input():
	return sys.stdin.readline()

def solve():
	(n, m) = map(int, input().split())
	g = [[] for i in range(n)]
	for j in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	que = [0]
	distance = [0] * n
	visited = [False] * n
	visited[0] = True
	odd = 0
	while que:
		x = que.pop()
		for adjnode in g[x]:
			if visited[adjnode] == False:
				visited[adjnode] = True
				distance[adjnode] = distance[x] + 1
				if distance[adjnode] % 2 != 0:
					odd += 1
				que.append(adjnode)
	ans = []
	if odd <= n // 2:
		print(odd)
		print(*[v + 1 for v in range(n) if distance[v] % 2 != 0])
	else:
		even = n - odd
		print(even)
		print(*[v + 1 for v in range(n) if distance[v] % 2 == 0])
	return

def main():
	t = int(input())
	for i in range(t):
		solve()
	return
main()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

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

def bfs(g, st, color):
	visited = [0] * len(g)
	visited[st] = 1
	color[st] = 1
	queue = []
	queue.append(st)
	new = []
	while len(queue) != 0:
		s = queue.pop()
		new.append(s)
		for i in g[s]:
			if visited[i] == 0:
				color[i] = 1 - color[s]
				visited[i] = 1
				queue.append(i)
	return new

def solve():
	(n, m) = sep()
	graph = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = sep()
		graph[a].append(b)
		graph[b].append(a)
	color = [-1] * (n + 1)
	bfs(graph, 1, color)
	if color.count(1) > color.count(0):
		ans = []
		for i in range(1, n + 1):
			if color[i] == 0:
				ans.append(i)
		print(len(ans))
		print(' '.join((str(ans[i]) for i in range(len(ans)))))
	else:
		ans = []
		for i in range(1, n + 1):
			if color[i] == 1:
				ans.append(i)
		print(len(ans))
		print(' '.join((str(ans[i]) for i in range(len(ans)))))
testcase(int(inp()))


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

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

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


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


from collections import deque

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


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

class Unionfind:

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

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

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

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

	def count(self, x):
		return -self.par[self.root(x)]

def bfs():
	q = deque([0])
	color = [0] * n
	color[0] = 1
	while q:
		v = q.popleft()
		for nv in adj_list[v]:
			if color[nv] == 0:
				color[nv] = -color[v]
				q.append(nv)
	return color
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	uf = Unionfind(n)
	adj_list = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		if not uf.is_same(u - 1, v - 1):
			uf.unite(u - 1, v - 1)
			adj_list[u - 1].append(v - 1)
			adj_list[v - 1].append(u - 1)
	color = bfs()
	black = color.count(1)
	white = n - black
	ans = []
	if black < white:
		for i in range(n):
			if color[i] == 1:
				ans.append(i + 1)
	else:
		for i in range(n):
			if color[i] == -1:
				ans.append(i + 1)
	print(len(ans))
	print(*ans)


import math
from collections import defaultdict as dd

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


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

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

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


from sys import stdin, stdout
from collections import *
from math import ceil, floor, log
st = lambda : list(stdin.readline().strip())
li = lambda : list(map(int, stdin.readline().split()))
mp = lambda : map(int, stdin.readline().split())
inp = lambda : int(stdin.readline())
pr = lambda n: stdout.write(str(n) + '\n')
mod = 1000000007
INF = float('inf')

def solve():
	(n, m) = mp()
	d = {i: [] for i in range(1, n + 1)}
	deg = {i: 0 for i in range(1, n + 1)}
	for i in range(m):
		(a, b) = mp()
		deg[a] += 1
		deg[b] += 1
		d[a].append(b)
		d[b].append(a)
	ma = -1
	val = 0
	for i in deg:
		if deg[i] > ma:
			ma = deg[i]
			val = i
	v = [False for i in range(n + 1)]
	q = deque()
	q.append(val)
	v[val] = True
	while q:
		a = q.popleft()
		for i in d[a]:
			if not v[i]:
				print(i, a)
				v[i] = True
				q.append(i)
for _ in range(1):
	solve()


from collections import deque as queue
(n, m) = 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) = 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) = list(map(int, input().split()))
d = {i + 1: [] for i in range(n)}
for i in range(m):
	(a, b) = list(map(int, input().split()))
	d[a].append(b)
	d[b].append(a)
maxln = len(d[1])
maxel = 1
for i in d:
	if len(d[i]) > maxln:
		maxel = i
		maxln = len(d[i])
l = [maxel]
k = 0
visit = [0 for i in range(n)]
visit[maxel - 1] = 1
while k < len(l):
	for i in range(len(d[l[k]])):
		if visit[d[l[k]][i] - 1] == 0:
			print(d[l[k]][i], l[k])
			visit[d[l[k]][i] - 1] = 1
			l.append(d[l[k]][i])
	k += 1


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
from collections import deque
for _ in range(RI()):
	(n, m) = RMI()
	a = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = RMI()
		a[x].append(y)
		a[y].append(x)
	col = [-1] * (n + 1)
	col[1] = 1
	d = deque([1])
	vis = [0] * (n + 1)
	ans = [[], [1]]
	while d:
		p = d.popleft()
		for i in a[p]:
			if col[i] == -1:
				tog = 1 - col[p]
				col[i] = tog
				ans[tog].append(i)
				d.append(i)
	if len(ans[0]) <= n // 2:
		print(len(ans[0]))
		print(*ans[0])
	else:
		print(len(ans[1]))
		print(*ans[1])


from collections import deque
(n, m) = 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) = 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])


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


import sys
input = sys.stdin.readline
from collections import deque
inf = int(10000000000.0)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	edges = []
	color = [0] * n
	for _ in range(m):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		if color[a] == 0 and color[b] == 0:
			(color[a], color[b]) = (1, 2)
		elif color[a] == 0:
			color[a] = 1 if color[b] == 2 else 2
		elif color[b] == 0:
			color[b] = 1 if color[a] == 2 else 2
	(aa, bb) = ([], [])
	for i in range(n):
		if color[i] == 1:
			aa.append(i + 1)
		else:
			bb.append(i + 1)
	if len(aa) <= len(bb):
		print(len(aa))
		print(*aa)
	else:
		print(len(bb))
		print(*bb)


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

class Graph(object):

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

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

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

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

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

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

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


import sys
for q in range(int(input())):
	(n, m) = [int(i) for i in sys.stdin.readline().split()]
	data = [[]]
	for i in range(n):
		data.append([])
	for i in range(m):
		(a, b) = [int(i) for i in sys.stdin.readline().split()]
		data[a].append(b)
		data[b].append(a)
	layer = [a]
	i = 1
	found = {a}
	take1 = [a]
	take2 = []
	while len(layer) != 0:
		newl = []
		if i % 2 == 0:
			for l in layer:
				for v in data[l]:
					if v not in found:
						found.add(v)
						newl.append(v)
						take1.append(v)
		else:
			for l in layer:
				for v in data[l]:
					if v not in found:
						found.add(v)
						newl.append(v)
						take2.append(v)
		layer = newl
		i += 1
	tak = take1
	if len(take1) > n // 2:
		tak = take2
	print(len(tak))
	[print(t, end=' ') for t in tak]
	print()


def main():
	t = int(input())
	while t:
		t -= 1
		ax = [int(ai) for ai in input().split()]
		n = ax[0]
		m = ax[1]
		adj = [[] for _ in range(0, n)]
		for i in range(0, m):
			ay = [int(ai) for ai in input().split()]
			x = ay[0]
			y = ay[1]
			x -= 1
			y -= 1
			adj[x].append(y)
			adj[y].append(x)
		dist = [-1] * n
		q = [0]
		dist[0] = 0
		odd = []
		even = []
		for i in q:
			for j in adj[i]:
				if dist[j] == -1:
					q.append(j)
					dist[j] = dist[i] + 1
		for i in range(0, n):
			if dist[i] % 2 == 0:
				even.append(i + 1)
			else:
				odd.append(i + 1)
		if len(odd) < len(even):
			print(len(odd))
			for i in odd:
				print(i)
		else:
			print(len(even))
			for i in even:
				print(i)
import os
import sys
from io import BytesIO, IOBase
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			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

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
from types import GeneratorType

def bootstrap(func, stack=[]):

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


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


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


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


import sys
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
import heapq
mod = 10 ** 9 + 7

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

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


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

def switch_group(group):
	return 1 if group == 2 else 2
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	g = [[] for _ in range(n + 1)]
	for _ in range(m):
		(v, u) = [int(x) for x in input().split()]
		g[v].append(u)
		g[u].append(v)
	group = [0] * (n + 1)
	queue = deque()
	queue.append(1)
	group[1] = 1
	while queue:
		node = queue.popleft()
		for neighbor in g[node]:
			if group[neighbor] == 0:
				group[neighbor] = switch_group(group[node])
				queue.append(neighbor)
	c = group.count(1)
	selected = 1 if c < n - c else 2
	ans = []
	for i in range(1, n + 1):
		if group[i] == selected:
			ans.append(i)
	print(len(ans))
	print(*ans)


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

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


import 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 threading
sys.setrecursionlimit(200000)
threading.stack_size(10 ** 8)

def dfs(x, a):
	global v, adj, l, l1
	v[x] = 1
	if a == 1:
		l.append(x)
	else:
		l1.append(x)
	for i in adj[x]:
		if not v[i]:
			dfs(i, a ^ 1)

def main():
	global v, l, adj, l1
	q = int(input())
	for j in range(q):
		(n, m) = map(int, input().split())
		v = [0] * (n + 1)
		l = []
		l1 = []
		adj = []
		for i in range(n + 1):
			adj.append([])
		for i in range(m):
			(x, y) = map(int, input().split())
			adj[x].append(y)
			adj[y].append(x)
		dfs(1, 1)
		l.sort()
		l1.sort()
		if len(l) <= n // 2:
			print(len(l))
			print(*l)
		else:
			print(len(l1))
			print(*l1)
t = threading.Thread(target=main)
t.start()
t.join()


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


from collections import deque
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))

def input():
	return sys.stdin.readline().rstrip('\r\n')

class Unionfind:

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

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

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

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

	def count(self, x):
		return -self.par[self.root(x)]

def bfs():
	q = deque([0])
	color = [0] * n
	color[0] = 1
	while q:
		v = q.popleft()
		for nv in adj_list[v]:
			if color[nv] == 0:
				color[nv] = -color[v]
				q.append(nv)
	return color
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	uf = Unionfind(n)
	adj_list = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		if not uf.is_same(u - 1, v - 1):
			uf.unite(u - 1, v - 1)
			adj_list[u - 1].append(v - 1)
			adj_list[v - 1].append(u - 1)
	color = bfs()
	black = color.count(1)
	white = n - black
	ans = []
	if black < white:
		for i in range(n):
			if color[i] == 1:
				ans.append(i + 1)
	else:
		for i in range(n):
			if color[i] == -1:
				ans.append(i + 1)
	print(len(ans))
	print(*ans)


from collections import defaultdict

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

def union(parent, size, a, b):
	pa = find(parent, a)
	pb = find(parent, b)
	if size[pa] > size[pb]:
		size[pa] += size[pb]
		parent[pb] = pa
		size[pb] = 0
	else:
		size[pb] += size[pa]
		parent[pa] = pb
		size[pa] = 0
(n, m) = map(int, input().split())
parent = [i for i in range(n)]
size = [1 for i in range(n)]
connections = defaultdict(lambda : 0)
edges = []
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	connections[a] += 1
	connections[b] += 1
	edges.append((a, b))
max_connections = max(connections.values())
for k in connections:
	if connections[k] == max_connections:
		best_node = k
best_edges = list(filter(lambda x: best_node in x, edges))
other_edges = list(filter(lambda x: best_node not in x, edges))
edges = best_edges + other_edges
picked = []
i = 0
while len(picked) < n - 1 and i < len(edges):
	(a, b) = edges[i]
	if find(parent, a) != find(parent, b):
		union(parent, size, a, b)
		picked.append(edges[i])
	i += 1
for p in picked:
	print(p[0] + 1, p[1] + 1)


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


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_left

def bfs(x):
	stack = deque()
	stack.append([x, 0])
	while stack:
		(x, y) = stack.popleft()
		if x not in visited:
			visited.add(x)
			level[y % 2].append(x)
			for i in graph[x]:
				if i not in visited:
					stack.append([i, y + 1])
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = {i: set() for i in range(1, n + 1)}
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a].add(b)
		graph[b].add(a)
	level = [[], []]
	visited = set()
	bfs(1)
	if len(level[0]) > len(level[1]):
		print(len(level[1]))
		print(*level[1])
	else:
		print(len(level[0]))
		print(*level[0])


from sys import stdin
(t,) = map(int, stdin.readline().split())
for _ in range(t):
	(n, m) = map(int, stdin.readline().split())
	graph = [[] for _ in range(n + 1)]
	for _ in range(m):
		(a, b) = map(int, stdin.readline().split())
		graph[a].append(b)
		graph[b].append(a)
	s1 = []
	s2 = []
	visited = [False] * (n + 1)
	for u in range(1, n + 1):
		if not visited[u]:
			visited[u] = True
			s1.append(u)
			for v in graph[u]:
				if not visited[v]:
					visited[v] = True
					s2.append(v)
	if len(s1) > len(s2):
		print(len(s2))
		print(*s2)
	else:
		print(len(s1))
		print(*s1)


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


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

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


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


import sys

def dfs(graph, start=0):
	n = len(graph)
	(visited, finished, appended) = ([False] * n, [False] * n, [False] * n)
	gt = [[] for _ in range(n)]
	stack = [start]
	appended[0] = True
	while stack:
		start = stack[-1]
		if not visited[start]:
			visited[start] = True
			for child in graph[start]:
				if not appended[child]:
					gt[start].append(child)
					gt[child].append(start)
					appended[child] = True
					appended[start] = True
					stack.append(child)
		else:
			stack.pop()
			finished[start] = True
	return gt

def is_bipartite(graph):
	n = len(graph)
	color = [-1] * n
	for start in range(n):
		if color[start] == -1:
			color[start] = 0
			stack = [start]
			while stack:
				parent = stack.pop()
				for child in graph[parent]:
					if color[child] == -1:
						color[child] = 1 - color[parent]
						stack.append(child)
					elif color[parent] == color[child]:
						return (False, color)
	return (True, color)
inp = [int(x) for x in sys.stdin.read().split()]
ii = 0
t = inp[ii]
ii += 1
for _ in range(t):
	(n, m) = inp[ii:ii + 2]
	ii += 2
	g = [[] for _ in range(n)]
	for _ in range(m):
		a = inp[ii] - 1
		ii += 1
		b = inp[ii] - 1
		ii += 1
		g[a].append(b)
		g[b].append(a)
	(__, c) = is_bipartite(dfs(g))
	ones = c.count(1)
	zeroes = n - ones
	if ones <= zeroes:
		o = []
		for i in range(n):
			if c[i] == 1:
				o.append(str(i + 1))
		print(ones)
		print(' '.join(o))
	else:
		z = []
		for i in range(n):
			if c[i] == 0:
				z.append(str(i + 1))
		print(zeroes)
		print(' '.join(z))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
import threading
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')
kk = lambda : map(int, input().split())
k2 = lambda : map(lambda x: int(x) - 1, input().split())
ll = lambda : list(kk())
(n, m) = kk()
neighs = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = k2()
	neighs[u].append(v)
	neighs[v].append(u)
m = v = 0
for (i, ls) in enumerate(neighs):
	if len(ls) > m:
		(m, v) = (len(ls), i)
seen = {v}
nex = [v]
while nex:
	newn = []
	for no in nex:
		for nei in neighs[no]:
			if nei not in seen:
				seen.add(nei)
				print(nei + 1, no + 1)
				newn.append(nei)
	nex = newn


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)


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


from collections import defaultdict
from collections import deque

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


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

def compute_adj_list(edges):
	adj_list = defaultdict(list)
	for (src, dst) in edges:
		adj_list[src].append(dst)
		adj_list[dst].append(src)
	return adj_list

def solution(edges, n):
	adj_list = compute_adj_list(edges)
	visited = [False] * n
	states = [False] * n
	root = 0
	queue = deque()
	queue.append(root)
	visited[root] = True
	while queue:
		parent = queue.popleft()
		for child in adj_list[parent]:
			if not visited[child]:
				visited[child] = True
				states[child] = not states[parent]
				queue.append(child)
	num_nodes_with_true_state = sum(states)
	if num_nodes_with_true_state <= n / 2:
		ans = [str(i + 1) for (i, state) in enumerate(states) if state]
	else:
		ans = [str(i + 1) for (i, state) in enumerate(states) if not state]
	print(len(ans))
	sys.stdout.write(' '.join(ans) + '\n')
k = int(input())
for _ in range(k):
	(n, m) = [int(val) for val in input().split()]
	edges = []
	for _ in range(m):
		(src, dst) = [int(val) - 1 for val in input().split()]
		edges.append([src, dst])
	if m == 0:
		print(1)
		print(1)
	else:
		solution(edges, n)


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


from sys import stdin, stdout
import collections
import math
Q = int(input())
for q in range(Q):
	(N, M) = [int(x) for x in stdin.readline().split()]
	degree = {}
	for i in range(1, N + 1):
		degree[i] = []
	for i in range(M):
		(u, v) = [int(x) for x in stdin.readline().split()]
		degree[u].append(v)
		degree[v].append(u)
	visited = [0] * (N + 1)
	label = [0] * (N + 1)
	stack = [1]
	label[1] = 1
	ones = 0
	twos = 0
	while stack:
		p = stack.pop()
		visited[p] = 1
		for node in degree[p]:
			if visited[node] == 0:
				stack.append(node)
				if label[p] == 1:
					label[node] = 2
				else:
					label[node] = 1
	for i in range(1, N + 1):
		if label[i] == 1:
			ones += 1
		else:
			twos += 1
	if ones > twos:
		print(twos)
		for i in range(1, N + 1):
			if label[i] == 2:
				print(i, end=' ')
		print('', end='\n')
	else:
		print(ones)
		for i in range(1, N + 1):
			if label[i] == 1:
				print(i, end=' ')
		print('', end='\n')


from collections import deque
import sys
t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, sys.stdin.readline().split())
	g = [list() for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, sys.stdin.readline().split())
		g[u].append(v)
		g[v].append(u)
	Q = deque()
	Q.append((1, 0))
	vis = [0] * (n + 1)
	vis[1] = 1
	vt = [list(), list()]
	while len(Q) != 0:
		(u, l) = Q.popleft()
		vt[l].append(u)
		for v in g[u]:
			if vis[v] == 0:
				Q.append((v, l ^ 1))
				vis[v] = 1
	(i, j) = (0, 1)
	if len(vt[i]) > len(vt[j]):
		(i, j) = (j, i)
	print(len(vt[i]))
	print(*vt[i])


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

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


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, m) = I()
	g = [[] for i in range(n)]
	dg = [[0, i] for i in range(n)]
	for i in range(m):
		(x, y) = I()
		x -= 1
		y -= 1
		dg[x][0] += 1
		dg[y][0] += 1
		g[x].append(y)
		g[y].append(x)
	dg.sort(key=lambda x: [-x[0], -x[1]])
	an = []
	vis = [0] * n
	c = []
	for i in range(n):
		(x, u) = dg[i]
		if not vis[u]:
			vis[u] = 1
			for j in g[u]:
				if vis[j] == 0:
					c.append(j + 1)
				vis[j] = 1
			an.append(u + 1)
	if len(an) > n // 2:
		print(len(c))
		print(*c)
	else:
		print(len(an))
		print(*an)


from collections import *
import sys
input = sys.stdin.readline
v = [[], []]
visited = [False] * (2 * 10 ** 5)

def dfs(a, i, f):
	v[f].append(i + 1)
	d = deque()
	visited[i] = True
	d.append([i, not f])
	while d:
		(x, f) = d.popleft()
		for j in a[x]:
			if not visited[j]:
				v[f].append(j + 1)
				d.append([j, not f])
				visited[j] = True
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split(' ')]
	l = [set() for i in range(n)]
	for j in range(m):
		(x, y) = [int(i) for i in input().split(' ')]
		l[x - 1].add(y - 1)
		l[y - 1].add(x - 1)
	ans = []
	v = [[], []]
	visited = [False for i in range(n)]
	for i in range(n):
		if not visited[i]:
			dfs(l, i, 0)
	ans = v[0] if len(v[0]) <= n // 2 else v[1]
	print(len(ans))
	print(' '.join((str(e) for e in ans)))


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

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


import collections

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


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

class UnionFind:
	__slots__ = ['id']

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

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

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

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


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


from sys import stdin
from collections import *

def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return list(stdin.readline()[:-1])

class graph:

	def __init__(self, gdict=None):
		if gdict is None:
			gdict = defaultdict(list)
		(self.gdict, self.edges) = (gdict, [])

	def add_edge(self, node1, node2, w=None):
		if w != None:
			self.gdict[node1].append([node2, w])
			self.gdict[node2].append([node1, w])
		else:
			self.gdict[node1].append(node2)
			self.gdict[node2].append(node1)
		self.edges.append([node1, node2, w])

	def bfs_util(self, i):
		(visit, levels) = (defaultdict(int), defaultdict(list, {0: [i]}))
		(queue, visit[i]) = (deque([[i, 0]]), 1)
		while queue:
			(s, lev) = queue.popleft()
			for i in self.gdict[s]:
				if visit[i] == 0:
					queue.append([i, lev ^ 1])
					levels[lev ^ 1].append(i)
					visit[i] = 1
		if len(levels[0]) <= len(levels[1]):
			print(len(levels[0]))
			print(*levels[0])
		else:
			print(len(levels[1]))
			print(*levels[1])
for i in range(int(input())):
	(n, m) = arr_inp(1)
	g = graph()
	for j in range(m):
		(u, v) = arr_inp(1)
		g.add_edge(u, v)
	g.bfs_util(1)


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


from collections import deque

def bfs(s):
	global otv
	used = [0] * n
	used[s] = 1
	q = deque()
	q.append(s)
	while q:
		v = q.popleft()
		for i in f[v]:
			if used[i] == 1:
				continue
			otv.append([v, i])
			used[i] = 1
			q.append(i)
(n, m) = map(int, input().split())
f = [[-1] * 2 for j in range(n)]
count = [0] * n
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	if f[x] != [-1] * 2:
		f[x].append(y)
	else:
		f[x] = [y]
	if f[y] != [-1] * 2:
		f[y].append(x)
	else:
		f[y] = [x]
	count[x] += 1
	count[y] += 1
pos = count.index(max(count))
otv = []
bfs(pos)
for i in otv:
	print(i[0] + 1, i[1] + 1)


from collections import *

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


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


import sys
input = sys.stdin.readline

class Unionfind:

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

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

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

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

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


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


(n, m) = 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)
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 defaultdict

def go():
	global config
	(n, m) = map(int, input().split(' '))
	graph = []
	for i in range(n + 1):
		graph.append([])
	for _ in range(m):
		(a, b) = map(int, input().split(' '))
		graph[a].append(b)
		graph[b].append(a)
	visited = [False] * (n + 1)
	is_odd = [False] * (n + 1)
	queue = [0] * (n + 1)
	visited[1] = True
	queue[1] = 1
	nxt_empty = 2
	for i in range(1, n + 1):
		current = queue[i]
		for child in graph[current]:
			if not visited[child]:
				is_odd[child] = not is_odd[current]
				queue[nxt_empty] = child
				nxt_empty += 1
				visited[child] = True
	odd = even = 0
	for i in range(1, n + 1):
		if is_odd[i]:
			odd += 1
		else:
			even += 1
	o = []
	if odd > even:
		for i in range(1, n + 1):
			if not is_odd[i]:
				o.append(i)
	else:
		for i in range(1, n + 1):
			if is_odd[i]:
				o.append(i)
	return f"{len(o)}\n{' '.join((str(i) for i in o))}"
tests = int(input())
answers = ''
for t in range(tests):
	answers += go() + '\n'
print(answers)


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