Lunar New Year is approaching, and Bob decides to take a wander in a nearby park.

The park can be represented as a connected graph with $n$ nodes and $m$ bidirectional edges. Initially Bob is at the node $1$ and he records $1$ on his notebook. He can wander from one node to another through those bidirectional edges. Whenever he visits a node not recorded on his notebook, he records it. After he visits all nodes at least once, he stops wandering, thus finally a permutation of nodes $a_1, a_2, \ldots, a_n$ is recorded.

Wandering is a boring thing, but solving problems is fascinating. Bob wants to know the lexicographically smallest sequence of nodes he can record while wandering. Bob thinks this problem is trivial, and he wants you to solve it.

A sequence $x$ is lexicographically smaller than a sequence $y$ if and only if one of the following holds:   $x$ is a prefix of $y$, but $x \ne y$ (this is impossible in this problem as all considered sequences have the same length);  in the first position where $x$ and $y$ differ, the sequence $x$ has a smaller element than the corresponding element in $y$. 


-----Input-----

The first line contains two positive integers $n$ and $m$ ($1 \leq n, m \leq 10^5$), denoting the number of nodes and edges, respectively.

The following $m$ lines describe the bidirectional edges in the graph. The $i$-th of these lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), representing the nodes the $i$-th edge connects.

Note that the graph can have multiple edges connecting the same two nodes and self-loops. It is guaranteed that the graph is connected.


-----Output-----

Output a line containing the lexicographically smallest sequence $a_1, a_2, \ldots, a_n$ Bob can record.


-----Examples-----
Input
3 2
1 2
1 3

Output
1 2 3 

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

Output
1 4 3 2 5 

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

Output
1 4 3 7 9 8 6 5 2 10 



-----Note-----

In the first sample, Bob's optimal wandering path could be $1 \rightarrow 2 \rightarrow 1 \rightarrow 3$. Therefore, Bob will obtain the sequence $\{1, 2, 3\}$, which is the lexicographically smallest one.

In the second sample, Bob's optimal wandering path could be $1 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 5$. Therefore, Bob will obtain the sequence $\{1, 4, 3, 2, 5\}$, which is the lexicographically smallest one.

Source: codeforces | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

Shortest paths

Greedy algorithms

Data structures


Solutions:
from heapq import *
(n, m) = map(int, input().split())
vis = [0, 1] + [0] * (n - 1)
e = [[] for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
ans = []
h = [1]
while h:
	cur = heappop(h)
	ans.append(cur)
	for to in e[cur]:
		if not vis[to]:
			vis[to] = 1
			heappush(h, to)
print(*ans)


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

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

def ls():
	return list(map(int, list(input())))

def la():
	return list(input())

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

def dic(x):
	return defaultdict(lambda : x)

def isPrime(n):
	i = 2
	if n == 1:
		return False
	while i <= int(math.sqrt(n)):
		if n % i == 0:
			return False
		i = i + 1
	return True

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

def binarySearch(arr, x):
	(l, r) = (0, len(arr) - 1)
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return True
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return False
(n, m) = li()
g = defaultdict(list)
for _ in range(m):
	(x, y) = li()
	g[x].append(y)
	g[y].append(x)
for i in range(1, n + 1):
	g[i].sort()
visited = [False] * (n + 1)

def bfs(v):
	queue = [v]
	heapq.heapify(queue)
	visited[v] = True
	while len(queue) != 0:
		front = heapq.heappop(queue)
		print(front, end=' ')
		for c in g[front]:
			if not visited[c]:
				visited[c] = True
				heapq.heappush(queue, c)
bfs(1)


from queue import PriorityQueue

def read_nums():
	return [int(x) for x in input().split()]

def main():
	(num_nodes, num_edges) = read_nums()
	graph = [set() for _ in range(num_nodes + 1)]
	for _ in range(num_edges):
		(start, end) = read_nums()
		if start == end:
			continue
		graph[start].add(end)
		graph[end].add(start)
	queued = set()
	reached = set()
	res = []
	currently_reachable = PriorityQueue()
	currently_reachable.put_nowait(1)
	for _ in range(1, num_nodes + 1):
		next_node = currently_reachable.get_nowait()
		reached.add(next_node)
		res.append(next_node)
		for n in graph[next_node]:
			if n not in reached and n not in queued:
				currently_reachable.put_nowait(n)
				queued.add(n)
	if len(res) != num_nodes:
		raise RuntimeError('WRONG SIZE {} - {}'.format(len(res), num_nodes))
	print(' '.join(map(str, res)))
main()


from heapq import *
(n, m) = map(int, input().split())
graph = {}
for _ in range(m):
	(a, b) = map(int, input().split())
	graph.setdefault(a, set()).add(b)
	graph.setdefault(b, set()).add(a)
ans = []
visited = set()
heap = [1]
while heap:
	v = heappop(heap)
	if v in visited:
		continue
	visited.add(v)
	ans.append(v)
	for neighbour in graph[v]:
		heappush(heap, neighbour)
print(*ans)


import sys
from heapq import heappush, heappop
(n, e) = map(int, input().split())
dic = {}
for i in range(e):
	(start, end) = map(int, input().split())
	if start in dic:
		dic[start].append(end)
	else:
		dic[start] = [end]
	if end in dic:
		dic[end].append(start)
	else:
		dic[end] = [start]

def dfs(graph, start):
	(visited, heap) = (set(), [start])
	vlist = []
	while heap:
		vertex = heappop(heap)
		if vertex not in visited:
			visited.add(vertex)
			vlist.append(vertex)
			for adj in dic[vertex]:
				if adj not in visited:
					heappush(heap, adj)
	return vlist
print(*dfs(dic, 1))


import heapq
(n, m) = map(int, input().split())
vertexs = dict()
for i in range(1, n + 1):
	vertexs[i] = []
for j in range(m):
	(v, u) = map(int, input().split())
	if v != u:
		vertexs[v].append(u)
		vertexs[u].append(v)
vis = dict()
dp = [1]
vis[1] = True
answers = []
for i in range(n):
	next_v = heapq.heappop(dp)
	answers.append(next_v)
	vis[next_v] = True
	for u in vertexs[next_v]:
		if u not in vis:
			heapq.heappush(dp, u)
			vis[u] = True
print(*answers, sep=' ')


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

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

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

def main():
	t = 1
	rr = []
	for _ in range(t):
		(n, m) = LI()
		ab = [LI() for _ in range(m)]
		e = collections.defaultdict(set)
		for (a, b) in ab:
			e[a].add(b)
			e[b].add(a)
		v = [0] * (n + 1)
		v[1] = 1
		q = [1]
		r = []
		while q:
			c = heapq.heappop(q)
			r.append(c)
			for b in e[c]:
				if not v[b]:
					v[b] = 1
					heapq.heappush(q, b)
		rr.append(JA(r, ' '))
	return JA(rr, '\n')
print(main())


import heapq
(n, m) = map(int, input().split())
v = [list() for i in range(n)]
for i in range(m):
	(v1, v2) = map(int, input().split())
	v1 -= 1
	v2 -= 1
	v[v1].append(v2)
	v[v2].append(v1)
visited = [False] * n
totalVis = 0
seq = []
pq = heapq.heapify(seq)
totalVis = 1
visited[0] = True
ans = [1]
for i in range(len(v[0])):
	heapq.heappush(seq, v[0][i])
while totalVis < n:
	x = heapq.heappop(seq)
	while visited[x]:
		x = heapq.heappop(seq)
	ans.append(x + 1)
	visited[x] = True
	totalVis += 1
	for i in range(len(v[x])):
		if not visited[v[x][i]]:
			heapq.heappush(seq, v[x][i])
print(' '.join(map(str, ans)))


import heapq
from collections import defaultdict as dd
(n, m) = map(int, input().split())
d = dd(list)
for i in range(m):
	(u, v) = map(int, input().split())
	d[u].append(v)
	d[v].append(u)
hq = [1]
heapq.heapify(hq)
l = []
vis = [0] * (n + 1)
while hq:
	a = heapq.heappop(hq)
	l.append(a)
	vis[a] = 1
	for j in d[a]:
		if vis[j] == 0:
			heapq.heappush(hq, j)
			vis[j] = 1
print(*l)


from heapq import *
from collections import defaultdict
(n, m) = map(int, input().split(' '))
g = defaultdict(list)
visit = [0] * (n + 1)
ans = []
for i in range(m):
	(u, v) = map(int, input().split(' '))
	g[u].append(v)
	g[v].append(u)
q = [1]
visit[1] = 1
while q:
	u = heappop(q)
	ans.append(u)
	for i in g[u]:
		if visit[i] == 0:
			heappush(q, i)
			visit[i] = 1
print(' '.join(map(str, ans)))


import heapq
(n, m) = map(int, input().split())
vertices = [[] for i in range(n)]
for _ in range(m):
	(v1, v2) = map(int, input().split())
	vertices[v1 - 1].append(v2 - 1)
	vertices[v2 - 1].append(v1 - 1)
heap = []
heapq.heappush(heap, 0)
vis = set()
ans = []
while not len(heap) == 0:
	v = heapq.heappop(heap)
	vis.add(v)
	ans.append(v + 1)
	for node in vertices[v]:
		if not node in vis:
			vis.add(node)
			heapq.heappush(heap, node)
print(*ans)


from queue import PriorityQueue

def getVals(type=str):
	return list(map(type, input().split()))
(n, m) = getVals(int)
adj = [[] for i in range(n)]
for i in range(m):
	(u, v) = getVals(int)
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)

def solve(n, m):
	visit = [False for i in range(n)]
	ans = []
	visit[0] = True
	pque = PriorityQueue()
	pque.put(0)
	while not pque.empty():
		curr = pque.get()
		ans.append(curr + 1)
		for x in adj[curr]:
			if visit[x] == False:
				visit[x] = True
				pque.put(x)
	return ans
print(*solve(n, m))


from collections import deque
from heapq import *

def walk(start):
	check = set()
	que = [1]
	count = 0
	heapify(que)
	while count < n:
		node = heappop(que)
		if node not in check:
			global res
			res.append(node)
			check.add(node)
			count += 1
			for neigh in arr[node]:
				heappush(que, neigh)
(n, m) = map(int, input().split())
arr = {i: [] for i in range(1, n + 1)}
count = 0
res = []
for i in range(m):
	(b, e) = map(int, input().split())
	arr[b].append(e)
	arr[e].append(b)
walk(1)
print(*res)


from collections import defaultdict
import heapq

def inpl():
	return list(map(int, input().split()))
(N, M) = inpl()
Edge = defaultdict(lambda : [])
for _ in range(M):
	(a, b) = inpl()
	if a != b:
		Edge[a].append(b)
		Edge[b].append(a)
Ans = []
visited = set([1])
Candi = [1]
for _ in range(N):
	j = heapq.heappop(Candi)
	for k in Edge[j]:
		if k not in visited:
			visited.add(k)
			heapq.heappush(Candi, k)
	Ans.append(j)
print(*Ans)


import heapq as q
(n, m) = [int(x) for x in input().split()]
v = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = [int(x) for x in input().split()]
	v[x].append(y)
	v[y].append(x)
vis = [0] * (n + 1)
a = [1]
vis[1] = 1
ans = []
while a:
	u = q.heappop(a)
	ans.append(u)
	for i in range(len(v[u])):
		if vis[v[u][i]] == 0:
			q.heappush(a, v[u][i])
			vis[v[u][i]] = 1
print(*ans)


import heapq
(n, m) = map(int, input().split())
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)
visited = [False] * (n + 1)
pq = [1]
visited[1] = True
ans = []
while pq:
	x = heapq.heappop(pq)
	ans.append(x)
	for v in g[x]:
		if not visited[v]:
			heapq.heappush(pq, v)
			visited[v] = True
print(*ans)


import heapq

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

def rdi():
	return int(input())
(n, m) = rlist()
line = [list() for i in range(n)]
for i in range(m):
	(x, y) = rlist()
	line[x - 1].append(y - 1)
	line[y - 1].append(x - 1)
vs = list()
heapq.heappush(vs, 0)
was = set()
ans = []
while len(vs) != 0:
	v = heapq.heappop(vs)
	if v in was:
		continue
	was.add(v)
	ans.append(v + 1)
	for el in line[v]:
		if el not in was:
			heapq.heappush(vs, el)
print(*ans)


from heapq import heappush, heappop, heapify

class MinHeap:

	def __init__(self):
		self.heap = []

	def parent(self, i):
		return (i - 1) / 2

	def insertKey(self, k):
		heappush(self.heap, k)

	def extractMin(self):
		return heappop(self.heap)
heapObj = MinHeap()
from collections import defaultdict
graph = defaultdict(list)
(n, m) = map(int, input().split())
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
visited = [False] * n
heapObj.insertKey(0)
visited[0] = True
count = 0
while count != n:
	s = heapObj.extractMin()
	print(s + 1, end=' ')
	for i in graph[s]:
		if visited[i] == False:
			heapObj.insertKey(i)
			visited[i] = True
	count += 1
print()


from collections import defaultdict
from heapq import heappush, heappop
(n, m) = map(int, input().split())
adj = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
for (k, v) in adj.items():
	adj[k].sort()
v = [0] * (n + 1)
perm = []
q = [1]
v[1] = 1
while q:
	e = heappop(q)
	perm.append(e)
	for i in adj[e]:
		if not v[i]:
			v[i] = 1
			heappush(q, i)
print(*perm)


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

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

def li():
	return list(mi())
import heapq
(n, m) = mi()
g = [[] for i in range(n + 1)]
for i in range(m):
	(u, v) = mi()
	g[u].append(v)
	g[v].append(u)
vis = [0] * (n + 1)
vis[1] = 1
pq = [1]
ans = []
while pq:
	u = heapq.heappop(pq)
	ans.append(u)
	for v in g[u]:
		if not vis[v]:
			heapq.heappush(pq, v)
			vis[v] = 1
print(*ans)


from queue import PriorityQueue
(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)
r = []
visited = [False] * n
visited[0] = True
q = PriorityQueue()
q.put(0)
while not q.empty():
	u = q.get()
	r.append(u + 1)
	for el in g[u]:
		if not visited[el]:
			q.put(el)
			visited[el] = True
print(' '.join(map(str, r)))


from heapq import *
R = lambda : map(int, input().split())
(n, m) = R()
V = [0, 0] + [1] * n
g = [[] for _ in V]
for _ in [0] * m:
	(u, v) = R()
	g[u] += (v,)
	g[v] += (u,)
h = [1]
while h:
	u = heappop(h)
	print(u)
	for v in g[u]:
		if V[v]:
			V[v] = 0
			heappush(h, v)


from bisect import bisect

def search(d):
	lst = [1]
	mark = {i: False for i in range(1, n + 1)}
	(res, mark[1]) = ([], True)
	while lst:
		x = lst.pop(0)
		res.append(x)
		for (i, y) in enumerate(d[x]):
			if mark[y] == False:
				mark[y] = True
				item = bisect(lst, y)
				lst.insert(item, y)
	return res
from sys import stdin
a = lambda : stdin.readline().split()
(n, m) = map(int, a())
(d, di) = ({i: [] for i in range(1, n + 1)}, {})
for _ in range(m):
	(u, v) = map(int, a())
	if u == v:
		continue
	if di.get((u, v)) == None and di.get((v, u)) == None:
		di[u, v] = 1
	else:
		continue
	d[u].append(v)
	d[v].append(u)
print(*search(d))


from heapq import *
(n, m) = map(int, input().split())
g = {}
for _ in range(m):
	(u, v) = map(int, input().split())
	g.setdefault(u, set()).add(v)
	g.setdefault(v, set()).add(u)
d = []
V = set()
h = [1]
while h:
	v = heappop(h)
	if v in V:
		continue
	V.add(v)
	d.append(v)
	for u in g[v]:
		heappush(h, u)
print(*d)


import sys
import heapq
(n, m) = [int(tmp) for tmp in sys.stdin.readline().split()]
lsc = [set() for tmp in range(n + 1)]
for i in range(m):
	(u, v) = [int(tmp) for tmp in sys.stdin.readline().split()]
	lsc[u].add(v)
	lsc[v].add(u)
lms = [1] * n
lou = [0] * (n + 1)
lou[1] = 2
myheap = []
for v in lsc[1]:
	if lou[v] == 0:
		lou[v] = 1
		heapq.heappush(myheap, v)
for i in range(1, n, 1):
	nv = heapq.heappop(myheap)
	lms[i] = nv
	lou[nv] = 2
	for v in lsc[nv]:
		if lou[v] == 0:
			lou[v] = 1
			heapq.heappush(myheap, v)
print(*lms)


import sys
(MOD, mod) = (1000000007, 998244353)
sys.setrecursionlimit(1000000)
from collections import deque, Counter, OrderedDict, defaultdict
from heapq import nsmallest, nlargest, heapify, heappop, heappush, heapreplace

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
(n, m) = get_ints()
graph = defaultdict(list)
for i in range(m):
	(x, y) = get_ints()
	graph[x].append(y)
	graph[y].append(x)
result = []
heap = [1]
visited = [False] * (n + 1)
visited[1] = True
while heap:
	x = heappop(heap)
	result.append(x)
	for i in graph[x]:
		if not visited[i]:
			visited[i] = True
			heappush(heap, i)
print(*result)


import heapq
(n, m) = [int(x) for x in input().split()]
v = {}
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	if a in v:
		v[a].add(b)
	else:
		v[a] = set([b])
	if b in v:
		v[b].add(a)
	else:
		v[b] = set([a])
answer = []
park = [1]
used = set([1])
while n > 0:
	elem = heapq.heappop(park)
	answer.append(elem)
	for key in v[elem]:
		if key not in used:
			heapq.heappush(park, key)
			used.add(key)
	n -= 1
print(*answer)


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import Decimal
from decimal import *
from collections import defaultdict, deque
import heapq
from decimal import Decimal
getcontext().prec = 25
abcd = 'abcdefghijklmnopqrstuvwxyz'
MOD = pow(10, 9) + 7
BUFSIZE = 8192
from bisect import bisect_left, bisect_right

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')
(n, k) = map(int, input().split(' '))
g = [list() for i in range(n + 1)]
v = [False] * (n + 1)
for i in range(k):
	(x, y) = list(map(int, input().split(' ')))
	g[x].append(y)
	g[y].append(x)
for i in range(n + 1):
	g[i] = sorted(g[i], reverse=True)
ans = []
v[0] = True
for i in range(n + 1):
	if not v[i]:
		q = list()
		heapq.heapify(q)
		heapq.heappush(q, i)
		while q:
			x = heapq.heappop(q)
			if not v[x]:
				v[x] = True
				ans.append(x)
				for j in g[x]:
					if not v[j]:
						heapq.heappush(q, j)
print(*ans)


import heapq

def main():
	(n, m) = map(int, input().split())
	graph_dict = {}
	for _ in range(m):
		(u, v) = map(int, input().split())
		temp_list = graph_dict.get(u, [])
		temp_list.append(v)
		graph_dict[u] = temp_list
		temp_list = graph_dict.get(v, [])
		temp_list.append(u)
		graph_dict[v] = temp_list
	visit = [False] * (n + 1)
	(h, ret) = ([], [])
	heapq.heappush(h, 1)
	while h:
		u = heapq.heappop(h)
		if visit[u]:
			continue
		ret.append(u)
		visit[u] = True
		for v in graph_dict.get(u, []):
			if visit[v]:
				continue
			heapq.heappush(h, v)
	print(*ret)
main()


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

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

def Sn():
	return sys.stdin.readline().strip()
from heapq import heapify, heappop, heappush

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		(n, m) = In()
		d = defaultdict(list)
		ans = []
		for i in range(m):
			(a, b) = In()
			d[a].append(b)
			d[b].append(a)
		for x in d:
			d[x].sort()
		visit = [False] * (n + 1)
		heap = []
		heappush(heap, 1)
		while heap:
			node = heappop(heap)
			if visit[node]:
				continue
			visit[node] = True
			ans.append(node)
			for x in d[node]:
				if not visit[x]:
					heappush(heap, x)
		print(*ans)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	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 Counter
import heapq
import heapq
(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)
v = [0] * (n + 1)
q = [1]
v[1] = 1
while q:
	s = heapq.heappop(q)
	print(s, end=' ')
	for i in g[s]:
		if v[i] == 0:
			heapq.heappush(q, i)
			v[i] = 1


import sys
import collections
import heapq
data = sys.stdin.read().splitlines()
(n, m) = list(map(int, data[0].split()))
graph = collections.defaultdict(set)
for line in data[1:]:
	(a, b) = list(map(int, line.split()))
	graph[a].add(b)
	graph[b].add(a)
for node in graph:
	graph[node] = sorted(graph[node], reverse=True)
visited = [False] * (n + 1)
visited[1] = True
ans = []
queue = [1]
while True:
	cur = heapq.heappop(queue)
	ans.append(cur)
	if len(ans) == n:
		break
	for nei in graph[cur]:
		if not visited[nei]:
			visited[nei] = True
			heapq.heappush(queue, nei)
print(' '.join(map(str, ans)))


import heapq
from collections import defaultdict
d = defaultdict(list)
(n, m) = map(int, input().split())
for i in range(m):
	(a, b) = map(int, input().split())
	a = a - 1
	b = b - 1
	d[a].append(b)
	d[b].append(a)
vis = [0] * n
vis[0] = 1
print(1, end=' ')
l = []
for i in d[0]:
	if not vis[i]:
		heapq.heappush(l, i)
		vis[i] = 1
heapq.heapify(l)
while l:
	t = heapq.heappop(l)
	print(t + 1, end=' ')
	for i in d[t]:
		if not vis[i]:
			heapq.heappush(l, i)
			vis[i] = 1


import heapq as hq
(n, m) = map(int, input().split())
eg = [[] for _ in range(n + 1)]
for (x, y) in [map(int, input().split()) for _ in range(m)]:
	if x == y:
		continue
	eg[x].append(y)
	eg[y].append(x)
(q, ans, vis) = ([1], [], set())
while q:
	fa = hq.heappop(q)
	if fa in vis:
		continue
	ans.append(fa)
	vis.add(fa)
	for i in eg[fa]:
		hq.heappush(q, i)
print(' '.join(map(str, ans)))


import sys, heapq as h
input = sys.stdin.readline

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input().strip()

def listStr():
	return list(input().strip())
import collections as col
import math

def solve():
	(N, M) = getInts()
	graph = col.defaultdict(list)
	for m in range(M):
		(U, V) = getInts()
		graph[U].append(V)
		graph[V].append(U)
	path = [1]
	visited = set()
	visited.add(1)
	queue = []
	for x in graph[1]:
		if x not in visited:
			queue.append(x)
			visited.add(x)
	h.heapify(queue)
	while queue:
		s = h.heappop(queue)
		path.append(s)
		for neighbour in graph[s]:
			if neighbour not in visited:
				h.heappush(queue, neighbour)
				visited.add(neighbour)
	print(*path)
	return
solve()


from heapq import heappush, heappop
(n, m) = map(int, input().split())
E = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
Q = []
now = 0
heappush(Q, 0)
vis = [1] * n
vis[0] = 0
while len(Q) > 0:
	now = heappop(Q)
	print(now + 1, end=' ')
	for el in E[now]:
		if vis[el]:
			heappush(Q, el)
			vis[el] = 0


from heapq import heappop, heappush
(n, m) = map(int, input().split())
visited = [0, 0] + [1] * (n - 1)
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)
heap = [1]
while heap:
	v = heappop(heap)
	print(v)
	for i in g[v]:
		if visited[i]:
			visited[i] = 0
			heappush(heap, i)


from collections import defaultdict, deque
from heapq import heappush, heappop
(n, m) = map(int, input().split())
g = defaultdict(lambda : [])
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
visited = [False] * (n + 1)
visited[1] = True
res = []
pq = [1]
while pq:
	temp = heappop(pq)
	res.append(temp)
	for i in g[temp]:
		if not visited[i]:
			visited[i] = True
			heappush(pq, i)
print(*res)


import heapq, sys
path = dict()
input()
for line in sys.stdin:
	if line.strip() == '':
		break
	(n, m) = [int(i) for i in line.strip().split()]
	if n not in path:
		path[n] = [m]
	else:
		path[n].append(m)
	if m not in path:
		path[m] = [n]
	else:
		path[m].append(n)
ans = [1]
visited = set([1])
pq = path[1]
heapq.heapify(pq)
while len(pq) > 0:
	the_next = heapq.heappop(pq)
	if the_next not in visited:
		ans.append(the_next)
		visited.add(the_next)
		for i in path[the_next]:
			heapq.heappush(pq, i)
print(' '.join([str(i) for i in ans]))


from heapq import heappush, heappop
(n, m) = map(int, input().split())
adj = [[] for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
v = [False for i in range(n + 1)]
q = [1]
perm = []
v[1] = True
while q:
	e = heappop(q)
	perm += [e]
	for i in adj[e]:
		if not v[i]:
			v[i] = True
			heappush(q, i)
print(*perm)


from sys import *
from collections import defaultdict
from heapq import *

def inputs():
	return stdin.readline()
(n, m) = map(int, inputs().split())
d = defaultdict(list)
cnt = {}
dict = {}
parent = {}
ans = []
for i in range(m):
	(u, v) = map(int, inputs().split())
	d[u].append(v)
	d[v].append(u)
q = [1]
dict[1] = True
ans = []
cnt[1] = True
while q:
	s = heappop(q)
	ans.append(s)
	for neighbor in d[s]:
		if neighbor not in cnt and neighbor not in dict:
			heappush(q, neighbor)
			dict[neighbor] = True
print(*ans)


import queue
(n, m) = map(int, input().split())
g = [set() for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].add(b - 1)
	g[b - 1].add(a - 1)
q = queue.PriorityQueue()
q.put(0)
visited = set()
sq = []
while len(visited) != n:
	node = q.get()
	if node not in visited:
		visited.add(node)
		sq.append(node)
	else:
		continue
	for nxt in g[node]:
		q.put(nxt)
print(' '.join(list(map(lambda x: str(x + 1), sq))))


import queue

class G:

	def __init__(self, n):
		self.V = [[] for x in range(n)]

	def Add(self, u, v):
		self.V[u - 1].append(v)
		self.V[v - 1].append(u)

	def __len__(self):
		return len(self.V)
(n, m) = (int(x) for x in input().split())
g = G(n)
mi = 10 ** 5
for q in range(m):
	(u, v) = (int(x) for x in input().split())
	g.Add(u, v)
	mi = min(mi, min(u, v))
output = ''
visit = [False] * len(g)
q = queue.PriorityQueue()
q.put(mi)
visit[mi - 1] = True
while not q.empty():
	u = q.get()
	for v in g.V[u - 1]:
		if not visit[v - 1]:
			q.put(v)
			visit[v - 1] = True
	output += '%s ' % u
print(output[:-1])


import sys
import heapq
input = sys.stdin.readline
(n, m) = map(int, input().split())
EDGE = [list(map(int, input().split())) for i in range(m)]
EDGELIST = [[] for i in range(n + 1)]
for (x, y) in EDGE:
	EDGELIST[x].append(y)
	EDGELIST[y].append(x)
NOW = EDGELIST[1]
heapq.heapify(NOW)
check = [0] * (n + 1)
ANS = [1]
check[1] = 1
while NOW:
	x = heapq.heappop(NOW)
	if check[x] == 1:
		continue
	else:
		ANS.append(x)
		check[x] = 1
		for e in EDGELIST[x]:
			if check[e] == 0:
				heapq.heappush(NOW, e)
for a in ANS:
	print(a, end=' ')


import heapq
(a, b) = list(input().split(' '))
a = int(a)
b = int(b)
g = [[] for i in range(a)]
for i in range(b):
	(u, v) = list(input().split(' '))
	u = int(u) - 1
	v = int(v) - 1
	g[u] += [v]
	g[v] += [u]
visited = [False for i in range(a)]
for j in range(a):
	if visited[j] == False:
		l = [j]
		heapq.heapify(l)
		ans = []
		while len(l) != 0:
			u = heapq.heappop(l)
			visited[u] = True
			ans += [u + 1]
			for i in g[u]:
				if visited[i] == True:
					continue
				heapq.heappush(l, i)
				visited[i] = True
for i in ans:
	print(i, end=' ')
print()


from collections import defaultdict
from heapq import heappop, heappush

def bfs(k):
	q = [k]
	vis[k] = 1
	while len(q):
		curr = heappop(q)
		p.append(curr + 1)
		for c in v[curr + 1]:
			if vis[c - 1] == 0:
				heappush(q, c - 1)
				vis[c - 1] = 1
(n, m) = map(int, input().split())
v = defaultdict(list)
vis = [0] * n
p = []
for i in range(m):
	(a, b) = map(int, input().split())
	v[a].append(b)
	v[b].append(a)
bfs(0)
print(*p)


import heapq

def dfs(arr, n, m):
	adjList = [[] for _ in range(n + 1)]
	visited = [False for _ in range(n + 1)]
	result = []
	for i in range(len(arr)):
		pair = arr[i]
		adjList[pair[0]].append(pair[1])
		adjList[pair[1]].append(pair[0])
	traversal(adjList, visited, result, 1)
	for j in range(len(result)):
		print(result[j])

def traversal(adjList, visited, result, start):
	queue = []
	heapq.heappush(queue, start)
	visited[start] = True
	while len(queue) > 0:
		item = heapq.heappop(queue)
		result.append(item)
		for i in range(len(adjList[item])):
			if visited[adjList[item][i]] == False:
				heapq.heappush(queue, adjList[item][i])
				visited[adjList[item][i]] = True
firstLine = input().split(' ')
(n, m) = (int(firstLine[0]), int(firstLine[1]))
edges = []
for i in range(m):
	secondLine = input().split(' ')
	(u, v) = (int(secondLine[0]), int(secondLine[1]))
	pair = [u, v]
	edges.append(pair)
dfs(edges, n, m)


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter, OrderedDict
import threading
from heapq import *

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)
	visit = [0] * n
	visit[0] = 1
	q = deque([0])
	eq = []
	ans = [1]
	while q:
		x = q.popleft()
		for nx in adj[x]:
			if not visit[nx]:
				heappush(eq, nx)
				visit[nx] = 1
		if len(eq):
			nx = heappop(eq)
			ans.append(nx + 1)
			q.append(nx)
	print(*ans)
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()


from heapq import *
(n, m) = map(int, input().split())
d = []
for i in range(n + 1):
	d.append([])
for i in range(m):
	(a, b) = map(int, input().split())
	d[a].append(b)
	d[b].append(a)
vis = [0, 0] + [1] * n
oldv = [1]
while oldv:
	act = heappop(oldv)
	print(act)
	for a in d[act]:
		if vis[a] == 1:
			vis[a] = 0
			heappush(oldv, a)


from heapq import heappop, heappush
(n, m) = map(int, input().split())
vis = [0] * 2 + [1] * (n - 1)
A = []
for i in range(n + 1):
	A.append([])
for i in range(m):
	(x, y) = map(int, input().split())
	A[x].append(y)
	A[y].append(x)
rec = [1]
while rec:
	pos = heappop(rec)
	print(pos)
	for i in A[pos]:
		if vis[i]:
			vis[i] = 0
			heappush(rec, i)


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

def bfs():
	visited = [0 for i in range(n + 1)]
	he = [1]
	container = []
	while he:
		q = heapq.heappop(he)
		if visited[q] == 1:
			continue
		visited[q] = 1
		container.append(q)
		for i in graph[q]:
			if visited[i] == 0:
				heapq.heappush(he, i)
	print(*container)
(n, m) = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
bfs()


from collections import defaultdict, deque
from bisect import insort
(n, m) = map(int, input().split())
d = defaultdict(list)
visited = [False] * (n + 1)
for _ in range(m):
	(u, v) = map(int, input().split())
	insort(d[u], v)
	insort(d[v], u)
z = deque([1])
visited[1] = True
while z:
	front = z.popleft()
	print(front, end=' ')
	for i in d[front]:
		if not visited[i]:
			insort(z, i)
			visited[i] = True


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))

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 Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
(n, e) = ilele()
d = {i: set() for i in range(n + 1)}
for _ in range(e):
	(a, b) = ilele()
	d[a].add(b)
	d[b].add(a)
q = [1]
heapq.heapify(q)
curr = 1
visited = [False] * (n + 1)
order = []
while len(q) > 0:
	curr = heapq.heappop(q)
	if visited[curr]:
		continue
	visited[curr] = True
	order.append(str(curr))
	for i in d[curr]:
		if visited[i]:
			continue
		heapq.heappush(q, i)
print(' '.join(order))


import sys
import heapq
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)
que = [0]
heapq.heapify(que)
ans = []
used = [0] * n
for i in range(n):
	a = heapq.heappop(que)
	while used[a] == 1:
		a = heapq.heappop(que)
	used[a] = 1
	ans.append(a + 1)
	for j in g[a]:
		if used[j] == 0:
			heapq.heappush(que, j)
print(*ans)


from queue import PriorityQueue
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
vis = [False for i in range(n)]
ans = []
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
Q = PriorityQueue()
Q.put(0)
while not Q.empty():
	node = Q.get()
	if vis[node]:
		continue
	vis[node] = True
	ans.append(node + 1)
	for adj in g[node]:
		Q.put(adj)
print(*ans)


from collections import defaultdict
import heapq
(n, m) = list(map(int, input().split()))
d = defaultdict(list)
for i in range(m):
	(x, y) = map(int, input().split())
	d[x].append(y)
	d[y].append(x)
for i in d:
	d[i].sort()
ans = []
visited = [0] * (n + 1)
l = [1]
visited[1] = 1
heapq.heapify(l)
while l:
	i = heapq.heappop(l)
	ans.append(i)
	for j in d[i]:
		if visited[j] == 0:
			visited[j] = 1
			heapq.heappush(l, j)
print(*ans)


import heapq
(n, m) = map(int, input().split())
dicto = {}
for i in range(m):
	(a, b) = map(int, input().split())
	if a in dicto:
		dicto[a].append(b)
	else:
		dicto[a] = [b]
	if b in dicto:
		dicto[b].append(a)
	else:
		dicto[b] = [a]
visited = [0] * (n + 1)
heap = [1]
visited[1] = 1
while len(heap) > 0:
	ver = heapq.heappop(heap)
	print(ver, end=' ')
	temp_l = dicto[ver]
	for i in range(len(temp_l)):
		if visited[temp_l[i]] == 0:
			heapq.heappush(heap, temp_l[i])
			visited[temp_l[i]] = 1


from sys import stdin
import heapq
input = stdin.readline
(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)
hq = [0]
vis = [False] * n
vis[0] = True
ans = []
while hq:
	ver = heapq.heappop(hq)
	ans.append(ver)
	for to in g[ver]:
		if not vis[to]:
			vis[to] = True
			heapq.heappush(hq, to)
for i in range(len(ans)):
	ans[i] += 1
print(*ans)


from sys import stdin, stdout, setrecursionlimit
import threading
from queue import PriorityQueue

class Tail_Recursion_Optimization:

	def __init__(self, RECURSION_LIMIT, STACK_SIZE):
		setrecursionlimit(RECURSION_LIMIT)
		threading.stack_size(STACK_SIZE)
		return None

class SOLVE:

	def solve(self):
		R = stdin.readline
		W = stdout.write
		ans = []
		(n, m) = [int(x) for x in R().split()]
		node = [[] for i in range(n + 1)]
		for i in range(m):
			(u, v) = [int(x) for x in R().split()]
			node[u].append(v)
			node[v].append(u)
		added = [None for i in range(n + 1)]
		added[1] = True
		priority_queue = PriorityQueue()
		ans.append('1')
		for v in node[1]:
			priority_queue.put(v)
		while not priority_queue.empty():
			u = priority_queue.get()
			if added[u] == None:
				added[u] = True
				ans.append(str(u))
				for v in node[u]:
					priority_queue.put(v)
		W(' '.join(ans))
		return 0

def main():
	s = SOLVE()
	s.solve()
threading.Thread(target=main).start()


import sys
input = sys.stdin.readline
from heapq import *
(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)
pq = [0]
ans = []
flag = [False] * n
flag[0] = True
while pq:
	v = heappop(pq)
	ans.append(v)
	for nv in G[v]:
		if not flag[nv]:
			heappush(pq, nv)
			flag[nv] = True
print(*list(map(lambda x: x + 1, ans)))


from collections import defaultdict
import heapq
(n, m) = map(int, input().split())
edgelist = defaultdict(lambda : [])
for _ in range(m):
	(u, v) = map(int, input().split())
	edgelist[u].append(v)
	edgelist[v].append(u)
seen = set([1])
queue = [1]
output = []
while queue:
	u = heapq.heappop(queue)
	output.append(u)
	for v in edgelist[u]:
		if v not in seen:
			seen.add(v)
			heapq.heappush(queue, v)
print(*output)


from heapq import heappush, heappop
(n, m) = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
st = set()
hp = []
v = [False for _ in range(n)]
heappush(hp, 0)
v[0] = True
ans = []
while hp:
	x = heappop(hp)
	ans += [x]
	for i in adj[x]:
		if v[i]:
			continue
		v[i] = True
		heappush(hp, i)
print(*[i + 1 for i in ans])


from collections import defaultdict, deque
from bisect import insort
from sys import stdin, stdout
input = stdin.readline
print = stdout.write
(n, m) = map(int, input().split())
d = defaultdict(list)
visited = [False] * (n + 1)
for _ in range(m):
	(u, v) = map(int, input().split())
	insort(d[u], v)
	insort(d[v], u)
z = deque([1])
visited[1] = True
while z:
	front = z.popleft()
	print(str(front) + ' ')
	for i in d[front]:
		if not visited[i]:
			insort(z, i)
			visited[i] = True


import heapq
(n, m) = map(int, input().split())
d = {}
for i in range(m):
	(u, v) = map(int, input().split())
	if u != v:
		if u not in d:
			d[u] = {v}
		else:
			d[u].add(v)
		if v not in d:
			d[v] = {u}
		else:
			d[v].add(u)
stack = [1]
ans = []
visited = {1}
while stack:
	p = heapq.heappop(stack)
	ans.append(p)
	if p in d:
		for x in d[p]:
			if x not in visited:
				heapq.heappush(stack, x)
				visited.add(x)
print(*ans)


from collections import defaultdict
import heapq
(n, m) = map(int, input().split())
visited = [False] * (n + 1)
ans = []
adj_list = defaultdict(set)
pq = []
while m:
	m -= 1
	(u, v) = map(int, input().split())
	if u != v:
		adj_list[u].add(v)
		adj_list[v].add(u)
heapq.heappush(pq, 1)
visited[1] = True
while len(pq):
	pop = heapq.heappop(pq)
	ans.append(str(pop))
	for i in adj_list[pop]:
		if not visited[i]:
			heapq.heappush(pq, i)
			visited[i] = True
print(' '.join(ans))


from heapq import heappop, heappush
(n, m) = map(int, input().split())
ans = []
explo = set()
graph = [set() for i in range(n + 2)]
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a].add(b)
	graph[b].add(a)
hea = [1]
while hea:
	cur = heappop(hea)
	if cur not in explo:
		ans.append(cur)
		explo.add(cur)
		for v in graph[cur]:
			heappush(hea, v)
print(*ans)


from heapq import *
(N, m) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(m):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
vis = [False] * N
rec = []
que = [0]
vis[0] = True
while que:
	q = heappop(que)
	rec.append(q)
	for w in G[q]:
		if not vis[w]:
			vis[w] = True
			heappush(que, w)
print(' '.join(map(lambda x: str(int(x) + 1), rec)))


from sys import stdin, stdout
import collections, heapq, bisect, math
input = stdin.readline

def rint():
	return int(input())

def rstr():
	return input().strip()

def rlstr():
	return list(input().strip().split())

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

def main():
	(n, m) = rlint()
	graph = collections.defaultdict(list)
	for _ in range(m):
		(u, v) = rlint()
		u -= 1
		v -= 1
		graph[u].append(v)
		graph[v].append(u)
	visit = [False] * n
	visit[0] = True
	heap = [0]
	while heap:
		u = heapq.heappop(heap)
		print(u + 1, end=' ')
		for v in graph[u]:
			if not visit[v]:
				visit[v] = True
				heapq.heappush(heap, v)
	print()
main()


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

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

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

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

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

class IOWrapper(IOBase):

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

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def bfs(s):
	vis = defaultdict(bool)
	vis[s] = True
	qu = [s]
	heapify(qu)
	while len(qu) != 0:
		e = heappop(qu)
		print(e, end=' ')
		for i in adj[e]:
			if vis[i] != True:
				heappush(qu, i)
				vis[i] = True
(n, e) = value()
adj = defaultdict(list)
for i in range(e):
	(u, v) = value()
	adj[u].append(v)
	adj[v].append(u)
bfs(1)


import heapq
(n, m) = map(int, input().split())
edge = [[] for i in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	edge[u].append(v)
	edge[v].append(u)
for i in range(1, n + 1):
	edge[i].sort()
visited = [False] * (n + 1)

def bfs(v):
	queue = [v]
	heapq.heapify(queue)
	visited[v] = True
	while queue != []:
		current_node = heapq.heappop(queue)
		print(current_node, end=' ')
		for c in edge[current_node]:
			if not visited[c]:
				visited[c] = True
				heapq.heappush(queue, c)
bfs(1)


import heapq
(a, b) = list(map(int, input().split()))
path = {}
for _ in range(b):
	(d, e) = list(map(int, input().split()))
	path.setdefault(d, []).append(e)
	path.setdefault(e, []).append(d)
ans = []
visited = set()
ins = [1]
while ins:
	u = heapq.heappop(ins)
	if u not in visited:
		ans.append(u)
		visited.add(u)
		for j in path[u]:
			heapq.heappush(ins, j)
print(*ans)


import heapq

def dfs(graph, visited, heap):
	while heap:
		curr = heapq.heappop(heap)
		print(curr, end=' ')
		for i in graph[curr]:
			if visited[i] == 0:
				visited[i] = 1
				heapq.heappush(heap, i)
(n, m) = map(int, input().split())
graph = {}
for _ in range(m):
	(key, value) = map(int, input().split())
	if key in graph:
		graph[key].append(value)
	else:
		graph[key] = [value]
	if value in graph:
		graph[value].append(key)
	else:
		graph[value] = [key]
visited = [0 for _ in range(n + 1)]
heap = [1]
heapq.heapify(heap)
visited[1] = 1
dfs(graph, visited, heap)


import heapq
(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append([])
for i in range(m):
	(u, v) = map(int, input().split())
	l[u - 1].append(v)
	l[v - 1].append(u)
for i in range(n):
	l[i].sort()
visited = [False] * n
visited[0] = True
ans = '1 '
x = 1
temp = []
heapq.heapify(temp)
for i in range(n - 1):
	for j in l[x - 1]:
		if visited[j - 1] == False:
			heapq.heappush(temp, j)
			visited[j - 1] = True
	x = heapq.heappop(temp)
	ans += str(x) + ' '
print(ans)


from heapq import heappop, heappush
(n, m) = list(map(int, input().split()))
a = []
as_ = set()
g = [set() for _ in range(n + 2)]
for _2 in range(m):
	(u, v) = list(map(int, input().split()))
	g[u].add(v)
	g[v].add(u)
h = [1]
while h:
	u = heappop(h)
	if u not in as_:
		a.append(u)
		as_.add(u)
		for v in g[u]:
			heappush(h, v)
print(*a)


from heapq import heappop, heappush
import sys
(N, M) = map(int, input().split())
edges = [[] for _ in [0] * N]
for (u, v) in (map(int, l.split()) for l in sys.stdin):
	edges[u - 1].append(v - 1)
	edges[v - 1].append(u - 1)
visited = [0] * N
ans = []
heap = [0]
ans_append = ans.append
while heap:
	v = heappop(heap)
	visited[v] = 1
	ans_append(v + 1)
	edges[v].sort()
	for to_v in edges[v]:
		if visited[to_v]:
			continue
		visited[to_v] = 1
		heappush(heap, to_v)
print(*ans)


import math
import bisect as bis
import heapq
(n, m) = map(int, input().split())
ed = []
for c in range(n + 1):
	ed.append([])
for i in range(m):
	(x, y) = map(int, input().split())
	ed[x].append(y)
	ed[y].append(x)
visited = [0] * (n + 1)
res = [1]
visited[1] = 1
h = []
heapq.heapify(h)
for e in ed[1]:
	if e != 1:
		heapq.heappush(h, e)
while len(h) > 0:
	m = heapq.heappop(h)
	if visited[m] == 1:
		continue
	res.append(m)
	visited[m] = 1
	for e in ed[m]:
		if visited[e] != 1:
			heapq.heappush(h, e)
for e in res:
	print(e, end=' ')


from heapq import *
input = __import__('sys').stdin.readline
(n, m) = map(int, input().split())
g = [[] for i in range(n + 1)]
for i in range(m):
	(v, u) = map(int, input().split())
	g[v].append(u)
	g[u].append(v)
was = [0] * (n + 1)
was[1] = 1
pq = [1]
while pq:
	f = heappop(pq)
	print(f, end=' ')
	for i in g[f]:
		if not was[i]:
			heappush(pq, i)
			was[i] = 1


import heapq
tmp = input().split()
n = int(tmp[0])
m = int(tmp[1])
point = {}
for i in range(n):
	point[i + 1] = []
for i in range(m):
	tmp = input().split()
	a = int(tmp[0])
	b = int(tmp[1])
	if a != b:
		x = min(a, b)
		b = max(a, b)
		a = x
		try:
			x = dict([a, b])
		except:
			point[a].append(b)
			point[b].append(a)
dict = {}
for i in range(n):
	dict[i + 1] = 1
dict[1] = 0
l = []
size = 1
l.append(1)
heapq.heapify(l)
while 1:
	x = heapq.heappop(l)
	size -= 1
	print(x, end=' ')
	for i in point[x]:
		if dict[i]:
			dict[i] = 0
			heapq.heappush(l, i)
			size += 1
	if size == 0:
		break


from heapq import *
(n, m) = map(int, input().split())
grid = [[] for x in range(300010)]
for i in range(m):
	(x, y) = map(int, input().split())
	grid[x].append(y)
	grid[y].append(x)
vis = [False for x in range(300010)]
vis[1] = True
pq = [1]
heapify(pq)
while pq != []:
	cur = heappop(pq)
	print(cur, end=' ')
	for p in grid[cur]:
		if not vis[p]:
			heappush(pq, p)
			vis[p] = True


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

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

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
(n, m) = inpl()
g = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = inpl_1()
	g[x].append(y)
	g[y].append(x)
res = []
q = []
heappush(q, 0)
seen = [False] * n
seen[0] = True
while q:
	now = heappop(q)
	res.append(now + 1)
	for v in g[now]:
		if seen[v]:
			continue
		seen[v] = True
		heappush(q, v)
print(*res)


def bfs(G, visited, s):
	from queue import PriorityQueue
	Q = PriorityQueue()
	visited[s] = True
	Q.put(s)
	res = []
	while not Q.empty():
		u = Q.get()
		res.append(u)
		for v in G[u]:
			if not visited[v]:
				visited[v] = True
				Q.put(v)
	return res
(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)
n = len(G)
visited = [False for _ in range(n)]
res = bfs(G, visited, 1)
print(*res)


from sys import stdin, stdout, setrecursionlimit
from heapq import heappush, heappop

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

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

def INS():
	return stdin.readline()

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

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

def OPL(ans):
	[stdout.write(str(_) + ' ') for _ in ans]
	stdout.write('\n')
(n, m) = INL()
X = [[] for _ in range(100005)]
for _ in range(m):
	(u, v) = INL()
	X[u].append(v)
	X[v].append(u)
V = [False for _ in range(n + 1)]
H = []
ANS = []
heappush(H, 1)
V[1] = True
while H:
	x = heappop(H)
	ANS.append(x)
	for _ in X[x]:
		if not V[_]:
			heappush(H, _)
			V[_] = True
OPL(ANS)


import sys
from heapq import heappush, heappop
from collections import defaultdict as dd

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

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

def input():
	return sys.stdin.readline().strip('\n')
visited = [0] * (10 ** 5 + 10)
l = dd(list)
queue = []
ans = []

def bfs():
	c = 1
	while c != 0:
		vertex = heappop(queue)
		c -= 1
		ans.append(vertex)
		visited[vertex] = 1
		for i in l[vertex]:
			if visited[i] == 0:
				heappush(queue, i)
				visited[i] = 1
				c += 1
(n, k) = get_ints()
for _ in range(k):
	(a, b) = get_ints()
	if a != b:
		l[a].append(b)
		l[b].append(a)
heappush(queue, 1)
bfs()
print(*ans)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

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

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
sys.setrecursionlimit(111111)
INF = 99999999999999999999999999999999

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, m) = ria()
		visited = [False] * (n + 1)
		graph = [[] for i in range(n + 1)]
		for i in range(m):
			(a, b) = ria()
			graph[a].append(b)
			graph[b].append(a)
		q = []
		heapify(q)
		heappush(q, 1)
		visited[1] = True
		ans = []
		while q:
			front = heappop(q)
			ans.append(front)
			for child in graph[front]:
				if not visited[child]:
					visited[child] = True
					heappush(q, child)
		wia(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			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, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			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()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

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

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import sys
from queue import PriorityQueue as prq

def input():
	return sys.stdin.readline().strip()
(n, m) = map(int, input().split())
minimum = 1
graf = {}
for i in range(m):
	(a, b) = map(int, input().split())
	if a != b or (a == b and b == 1):
		if a in graf:
			graf[a].add(b)
		else:
			graf[a] = set([b])
		if b in graf:
			graf[b].add(a)
		else:
			graf[b] = set([a])
ans = []
used = set()
och = prq(maxsize=0)
och.put(1)
s = set()
while len(used) != n:
	a = och.get()
	ans.append(a)
	used.add(ans[-1])
	s.add(a)
	for i in graf[ans[-1]]:
		if i not in s:
			s.add(i)
			och.put(i)
print(*ans)


import heapq
(n, m) = [int(i) for i in input().split()]
a = {i: set() for i in range(n)}
for i in range(m):
	(u, v) = [int(i) for i in input().split()]
	a[u - 1] |= {v - 1}
	a[v - 1] |= {u - 1}

def dfs(graph, start):
	(visited, stack) = (set(), [start])
	heapq.heapify(stack)
	while stack:
		v = heapq.heappop(stack)
		if v not in visited:
			visited.add(v)
			print(v + 1)
			for k in graph[v] - visited:
				heapq.heappush(stack, k)
	return visited
dfs(a, 0)


from heapq import heappush, heappop
(n, m) = map(int, input().split())
g = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	g[x].append(y)
	g[y].append(x)
vis = [0] * (n + 1)
(h, ans) = ([], [])
heappush(h, 1)
vis[1] = 1
while len(h):
	x = heappop(h)
	ans.append(x)
	for i in g[x]:
		if vis[i] == 0:
			heappush(h, i)
			vis[i] = 1
print(*ans)


from collections import defaultdict
from collections import deque
import heapq
(n, m) = map(int, input().split())
g = defaultdict(set)
for _ in range(m):
	(f, t) = map(int, input().split())
	g[f].add(t)
	g[t].add(f)
v = [1]
visited = {1}
candidates = []
for i in range(n - 1):
	node = v[i]
	for e in g[node]:
		if e in visited:
			continue
		else:
			heapq.heappush(candidates, e)
			visited.add(e)
	e = heapq.heappop(candidates)
	v.append(e)
print(' '.join(map(str, v)))


from math import *
from copy import *
from string import *
from random import *
from sys import stdin
from sys import maxsize
from heapq import *
from operator import *
from itertools import *
from collections import Counter
from collections import defaultdict

def bfs(adj, m):
	n = len(adj)
	q = [0]
	vis = [0] * n
	vis[0] = 1
	path = []
	while q != []:
		src = heappop(q)
		path.append(src + 1)
		for nn in adj[src]:
			if not vis[nn]:
				vis[nn] = 1
				heappush(q, nn)
	print(*path)
(N, M) = list(map(int, stdin.readline().rstrip().split()))
adj = [[] for i in range(N)]
for _ in range(M):
	(a, b) = list(map(int, stdin.readline().rstrip().split()))
	(a, b) = (a - 1, b - 1)
	adj[a].append(b)
	adj[b].append(a)
bfs(adj, M)


import sys, re, math
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from heapq import heappush, heappop, heapify, nlargest, nsmallest
import re

def STR():
	return list(input())

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

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

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

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

def sortListWithIndex(listOfTuples, idx):
	return sorted(listOfTuples, key=lambda x: x[idx])

def sortDictWithVal(passedDic):
	temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
	toret = {}
	for tup in temp:
		toret[tup[0]] = tup[1]
	return toret

def sortDictWithKey(passedDic):
	return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
global visited
final = '1'

def dfs(node):
	global final
	visited[node] = True
	for child in graph[node]:
		if visited[child] == False:
			final += ' ' + str(child)
			dfs(child)
(n, m) = MAP()
tempHeap = []
visited = [False] * (n + 1)
graph = defaultdict(list)
for _ in range(m):
	(temp1, temp2) = MAP()
	graph[temp1].append(temp2)
	graph[temp2].append(temp1)
heap = [1]
heapify(heap)
visited[1] = True
ans = ''
while heap:
	popped = heappop(heap)
	ans += str(popped) + ' '
	for child in graph[popped]:
		if visited[child] == False:
			heappush(heap, child)
			visited[child] = True
print(ans)


from __future__ import division, print_function
import cmath
import itertools
import math
import operator as op
import sys
from atexit import register
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
if sys.version_info[0] < 3:
	from io import BytesIO as stream
else:
	from io import StringIO as stream
if sys.version_info[0] < 3:

	class dict(dict):

		def items(self):
			return dict.iteritems(self)

		def keys(self):
			return dict.iterkeys(self)

		def values(self):
			return dict.itervalues(self)
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip

def sync_with_stdio(sync=True):
	global input, flush
	if sync:
		flush = sys.stdout.flush
	else:
		sys.stdin = stream(sys.stdin.read())
		input = lambda : sys.stdin.readline().rstrip('\r\n')
		sys.stdout = stream()
		register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def main():
	(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)
	seen = {1}
	o = [1]
	s = g[1][:]
	heapify(s)
	while s != []:
		a = heappop(s)
		while a in seen:
			if s == []:
				print(*o)
				exit()
			a = heappop(s)
		seen.add(a)
		o.append(a)
		for i in g[a]:
			heappush(s, i)
	print(*o)
sync_with_stdio(False)
main()


from collections import deque
import pdb
import heapq
from heapq import *
from pprint import pprint

def rI():
	return [int(i) for i in input().split()]
(n, m) = rI()
dat = [[] for i in range(n + 1)]
hh = [1]
for i in range(m):
	(a, b) = rI()
	dat[a].append(b)
	dat[b].append(a)
hhs = [False for i in range(n + 1)]
vis = [False for i in range(n + 1)]
hhs[1] = True
try:
	while 1:
		cur = heappop(hh)
		for i in dat[cur]:
			if hhs[i] == False:
				heappush(hh, i)
				hhs[i] = True
		print(cur, end=' ')
except Exception as e:
	exit()


from heapq import heapify, heappush, heappop
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	g[a].append(b)
	g[b].append(a)

def solve(n, g):
	res = []
	visited = [0] * n
	nodes = [0]
	heapify(nodes)
	visited[0] = 1
	while nodes:
		node = heappop(nodes)
		res.append(str(node + 1))
		for nb in g[node]:
			if not visited[nb]:
				heappush(nodes, nb)
				visited[nb] = 1
	return ' '.join(res)
print(solve(n, g))


from sys import stdin
import heapq
(n, m) = map(int, stdin.readline().strip().split())
adj = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, stdin.readline().strip().split())
	adj[a].append(b)
	adj[b].append(a)
s = [1]
ans = []
visited = [False for i in range(n + 1)]

def dfs(n):
	visited[n] = True
	ans.append(n)
	for i in adj[n]:
		if not visited[i]:
			heapq.heappush(s, i)
			visited[i] = True
while len(s) > 0:
	dfs(heapq.heappop(s))
print(*ans)


from queue import PriorityQueue
(n, m) = (int(i) for i in input().split(' '))
graph = []
for i in range(n + 1):
	graph.append([])
for i in range(m):
	(a, b) = (int(i) for i in input().split(' '))
	graph[a].append(b)
	graph[b].append(a)
visited = [0] * (n + 1)
visited[1] = 1
ans = [1]
reachables = PriorityQueue()
for i in graph[1]:
	reachables.put(i)
while len(ans) < n:
	i = reachables.get()
	if not visited[i]:
		visited[i] = 1
		ans.append(i)
		for j in graph[i]:
			if not visited[j]:
				reachables.put(j)
print(*ans)


import sys
input = sys.stdin.readline
from queue import PriorityQueue
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
e = {}
for i in range(m):
	(x, y) = map(int, input().split())
	if x != y and (x, y) not in e:
		e[x, y] = 1
		e[y, x] = 1
		graph[x - 1].append(y - 1)
		graph[y - 1].append(x - 1)
q = PriorityQueue()
vis = [0] * n
q.put(0)
while not q.empty():
	e = q.get()
	if vis[e]:
		continue
	vis[e] = 1
	print(e + 1, end=' ')
	for i in graph[e]:
		if not vis[i]:
			q.put(i)
print()


import heapq
(n, m) = map(int, input().split())
heap = []
arr = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	arr[a].append(b)
	arr[b].append(a)
answer = []
heap = [0]
used = {0}
while heap:
	v = heapq.heappop(heap)
	answer.append(v)
	for vi in arr[v]:
		if vi not in used:
			used.add(vi)
			heapq.heappush(heap, vi)
answer = [str(x + 1) for x in answer]
print(' '.join(answer))


import heapq
(n, m) = map(int, input().split())
gr = {}

class node:

	def __init__(self):
		self.adj = set()

	def ax(self, b):
		self.adj.add(b)
for i in range(1, n + 1):
	gr[i] = node()
for i in range(m):
	(u, v) = map(int, input().split())
	if u == v:
		continue
	gr[u].ax(v)
	gr[v].ax(u)
i = 1
v = [False for i in range(n + 1)]
path = []
l = 0
s = [i]
heapq.heapify(s)
while s:
	x = heapq.heappop(s)
	if v[x]:
		continue
	path.append(x)
	l += 1
	if l == n:
		print(*path)
		exit()
	v[x] = True
	for j in gr[x].adj:
		if v[j]:
			continue
		heapq.heappush(s, j)


import bisect

def dfs(i, vis, g):
	print(i, end=' ')
	vis[i] = 1
	for j in g[i]:
		if vis[j] == 0:
			dfs(j, vis, g)
(n, m) = map(int, input().split())
g = [[] for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	bisect.insort(g[u], v)
	bisect.insort(g[v], u)
bfs = [1]
l = 1
vis = [0] * (n + 1)
vis[1] = 1
while l != 0:
	i = bfs.pop(0)
	print(i, end=' ')
	l -= 1
	for j in g[i]:
		if vis[j] == 0:
			bisect.insort(bfs, j)
			vis[j] = 1
			l += 1
print()


from collections import defaultdict
import heapq
(n, m) = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
for i in range(n):
	graph[i].sort()
visited = [0 for i in range(n + 1)]
ans = []
q = []
heapq.heappush(q, 1)
visited[1] = 1
while q:
	v = heapq.heappop(q)
	ans.append(v)
	for i in graph[v]:
		if visited[i] == 0:
			heapq.heappush(q, i)
			visited[i] = 1
for i in ans:
	print(i, end=' ')
print('')


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
G = defaultdict(list)
(n, m) = Neo()
for i in range(m):
	(a, b) = Neo()
	G[a] += [b]
	G[b] += [a]
vis = [0] * (n + 1)
Ans = []

def hello(node):
	st = [node]
	heapify(st)
	vis[node] = 1
	while st:
		t = heappop(st)
		Ans.append(t)
		for i in G[t]:
			if not vis[i]:
				vis[i] = 1
				heappush(st, i)
hello(1)
print(*Ans)


from sys import stdin, stdout
from itertools import combinations
from collections import defaultdict, OrderedDict
import math
import heapq

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

def stringListIn():
	return [x for x in stdin.readline().split()]

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

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

def dfs(root, parent):
	vis[root] = 1
	q = [root]
	heapq.heapify(q)
	while q:
		r = heapq.heappop(q)
		res.append(r)
		lis = sorted(g[r])
		for i in range(len(lis)):
			if vis[lis[i]] == 0:
				heapq.heappush(q, lis[i])
				vis[lis[i]] = 1
(n, m) = listIn()
g = [[] for i in range(n + 1)]
for i in range(m):
	(u, v) = listIn()
	g[u].append(v)
	g[v].append(u)
vis = [0] * (n + 1)
res = []
dfs(1, -1)
print(*res)


from collections import defaultdict
import heapq
(n, m) = map(int, input().split())
gr = defaultdict(list)
for _ in range(m):
	(x, y) = map(int, input().split())
	gr[x].append(y)
	gr[y].append(x)
vis = [False] * (n + 1)
ans = []
q = [1]
vis[1] = True
heapq.heapify(q)
while q:
	x = heapq.heappop(q)
	ans.append(x)
	for i in gr[x]:
		if vis[i] == False:
			vis[i] = True
			heapq.heappush(q, i)
print(*ans)


import heapq as hq
(n, m) = map(int, input().split())
d = {}
for i in range(m):
	(x, y) = map(int, input().split())
	if x not in d:
		d[x] = []
	if y not in d:
		d[y] = []
	d[x].append(y)
	d[y].append(x)
ans = []
q = [1]
hq.heapify(q)
visit = (n + 1) * [0]
visit[1] = 1
while len(q) != 0:
	node = hq.heappop(q)
	ans.append(node)
	for i in d[node]:
		if visit[i] == 0:
			hq.heappush(q, i)
			visit[i] = 1
print(*ans)


import heapq
(n, m) = map(int, input().split())
s = [set() for i in range(n)]
ans = []
used = [False] * n
for i in range(m):
	(fro, to) = map(int, input().split())
	fro -= 1
	to -= 1
	s[fro].add(to)
	s[to].add(fro)
ss = []
heapq.heappush(ss, 0)
used[0] = True
while len(ss) > 0:
	v = heapq.heappop(ss)
	ans.append(v + 1)
	for el in s[v]:
		if not used[el]:
			heapq.heappush(ss, el)
			used[el] = True
print(*ans)


import heapq
(n, m) = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
(list, cnt) = ([], 0)
visited = [False] * (n + 1)
heap = [1]
while cnt < n:
	u = heapq.heappop(heap)
	if not visited[u]:
		visited[u] = True
		cnt += 1
		list.append(u)
		for v in adj[u]:
			if not visited[v]:
				heapq.heappush(heap, v)
print(' '.join(map(str, list)))


from collections import defaultdict

class Heap:

	def __init__(self, arr, key=None, heap_type='min'):
		self.arr = arr
		self.key = key
		self.heap_type = heap_type
		if key == None:
			self.key = lambda x: x
		self.heapify()

	def __repr__(self):
		return str(self.arr)

	def __compare(self, index1, index2):
		return self.__compare_keys(self[index1], self[index2])

	def __compare_keys(self, key1, key2):
		ans = 0
		if key1 > key2:
			ans = 1
		elif key1 < key2:
			ans = -1
		else:
			ans = 0
		return ans if self.heap_type == 'min' else -1 * ans

	def heapify(self):
		for i in range(0, len(self)):
			self.__bubble_up(i)

	def insert(self, item):
		self.arr.append(item)
		self.__bubble_up(len(self) - 1)

	def __getitem__(self, index):
		return self.key(self.arr[index])

	def __bubble_up(self, index):
		parent = (index - 1) // 2
		while parent >= 0 and self.__compare(index, parent) == -1:
			(self.arr[parent], self.arr[index]) = (self.arr[index], self.arr[parent])
			(index, parent) = (parent, (parent - 1) // 2)

	def __bubble_down(self, index):
		high = len(self)
		while True:
			(l, r) = (index * 2 + 1, index * 2 + 2)
			if r < high:
				if self.__compare(r, l) == -1:
					if self.__compare(r, index) >= 0:
						break
					(self.arr[r], self.arr[index]) = (self.arr[index], self.arr[r])
					index = r
				else:
					if self.__compare(l, index) >= 0:
						break
					(self.arr[l], self.arr[index]) = (self.arr[index], self.arr[l])
					index = l
			elif l < high:
				if self.__compare(l, index) >= 0:
					break
				(self.arr[l], self.arr[index]) = (self.arr[index], self.arr[l])
				break
			else:
				break

	def __len__(self):
		return len(self.arr)

	def pop(self):
		(self.arr[0], self.arr[-1]) = (self.arr[-1], self.arr[0])
		top = self.arr.pop(-1)
		self.__bubble_down(0)
		return top
(n, m) = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
lex = [1]
in_heap = [False] * n
in_heap[0] = True
cnt = 1
heap = Heap([])
for a in graph[0]:
	if not in_heap[a]:
		heap.insert(a)
		in_heap[a] = True
while cnt != n:
	v = heap.pop()
	lex.append(v + 1)
	cnt += 1
	for a in graph[v]:
		if not in_heap[a]:
			heap.insert(a)
			in_heap[a] = True
print(*lex)


import heapq
from collections import defaultdict
graph = defaultdict(list)
(n, m) = list(map(int, input().split()))
for i in range(m):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u].append(v)
	graph[v].append(u)
visited = [False for i in range(n)]
q = [0]
heapq.heapify(q)
visited[0] = True
while q != []:
	u = heapq.heappop(q)
	print(u + 1, end=' ')
	for v in graph[u]:
		if visited[v] == False:
			visited[v] = True
			heapq.heappush(q, v)


import heapq
(n, m) = map(int, input().split())
node = [[] for _ in range(n + 1)]
mark = [0 for _ in range(n + 1)]
queue = [0 for _ in range(n + 1)]
path = [1]
option = [1]
for i in range(m):
	(a, b) = map(int, input().split())
	heapq.heappush(node[a], b)
	heapq.heappush(node[b], a)
queue[1] = 1
location = 1
c = 0
for v in node[1]:
	queue[v] = 1
	heapq.heappush(option, v)
while len(option) > 0:
	if not mark[location]:
		mark[location] = 1
	next = heapq.heappop(option)
	if not mark[next]:
		for v in node[next]:
			if not queue[v]:
				queue[v] = 1
				heapq.heappush(option, v)
		path.append(next)
		location = next
print(*path)


from sys import stdin, stdout
from heapq import heappush, heappop

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

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

def INS():
	return stdin.readline()

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

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

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

def bootstrap(f, stack=[]):

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

@bootstrap
def dfs():
	x = heappop(H)
	ANS.append(x)
	for _ in X[x]:
		if not V[_]:
			heappush(H, _)
			V[_] = True
	if H:
		yield dfs()
	yield
(n, m) = INL()
X = [[] for _ in range(100005)]
for _ in range(m):
	(u, v) = INL()
	X[u].append(v)
	X[v].append(u)
V = [False for _ in range(n + 1)]
H = []
ANS = []
heappush(H, 1)
V[1] = True
dfs()
OPL(ANS)


from heapq import *
(n, m) = map(int, input().split(' '))
li = [[] for i in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split(' '))
	li[u].append(v)
	li[v].append(u)
ins = [1]
ard = set()
while ins:
	u = heappop(ins)
	if u not in ard:
		print(u, end=' ')
		ard.add(u)
		for j in li[u]:
			heappush(ins, j)


from collections import defaultdict
import heapq
graph = defaultdict(set)
(n, m) = map(int, input().split())
for _ in range(m):
	(a, b) = map(int, input().split())
	if a != b:
		graph[a].add(b)
		graph[b].add(a)
seen = {1}
hist = [1]
h = list(graph[1])
heapq.heapify(h)
while len(hist) < n:
	next_node = heapq.heappop(h)
	if next_node in seen:
		continue
	seen.add(next_node)
	hist.append(next_node)
	for node in graph[next_node]:
		heapq.heappush(h, node)
print(' '.join((str(x) for x in hist)))


import heapq
(n, m) = list(map(int, input().split()))
edges = [[] for _ in range(n + 1)]
for _ in range(m):
	(a, b) = list(map(int, input().split()))
	edges[a].append(b)
	edges[b].append(a)
heap = []
(visited, res) = ([0] * (n + 1), [])
heapq.heappush(heap, 1)
visited[1] = 1
while len(heap) > 0:
	cur = heapq.heappop(heap)
	res.append(cur)
	for adj in edges[cur]:
		if not visited[adj]:
			heapq.heappush(heap, adj)
			visited[adj] = 1
print(' '.join(map(str, res)))


import sys
import heapq
input = lambda : sys.stdin.readline().strip('\r\n')
(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 = []
vis = [0] * (n + 1)
h = [1]
vis[1] = 1
while h:
	cur = heapq.heappop(h)
	ans.append(cur)
	for child in g[cur]:
		if not vis[child]:
			vis[child] = 1
			heapq.heappush(h, child)
print(*ans)


import heapq
(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)
visited = [False] * (nVertexes + 1)
visited[1] = True
ret = []
q = [1]
while q:
	curV = heapq.heappop(q)
	ret.append(curV)
	for nextV in edges[curV]:
		if not visited[nextV]:
			visited[nextV] = True
			heapq.heappush(q, nextV)
print(*ret)


import heapq
(n, m) = map(int, input().split())
dic = {}
for i in range(1, n + 1):
	dic[i] = []
for i in range(m):
	(x, y) = map(int, input().split())
	dic[x].append(y)
	dic[y].append(x)
ans = []
count = 0
li = [1]
heapq.heapify(li)
stock = {1}
while count != n:
	el = heapq.heappop(li)
	count += 1
	ans.append(el)
	xx = dic[el]
	for i in xx:
		if not i in stock:
			heapq.heappush(li, i)
			stock.add(i)
print(*ans)


from collections import defaultdict
import heapq
import sys
(n, m) = map(int, sys.stdin.readline().split())
adjacency_map = defaultdict(set)
for edge in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	adjacency_map[u].add(v)
	adjacency_map[v].add(u)
visited = set()
visited.add(1)
path = []
min_heap = [1]
while min_heap:
	node = heapq.heappop(min_heap)
	path.append(node)
	for neighbor in adjacency_map[node]:
		if neighbor in visited:
			continue
		heapq.heappush(min_heap, neighbor)
		visited.add(neighbor)
for char in path:
	print(char, end=' ')


from heapq import *
(n, e) = map(int, input().split())
d = {i: set() for i in range(n + 1)}
for _ in range(e):
	(a, b) = map(int, input().split())
	d[a].add(b)
	d[b].add(a)
q = [1]
heapify(q)
curr = 1
visited = [False] * (n + 1)
order = []
while len(q) > 0:
	curr = heappop(q)
	if visited[curr]:
		continue
	visited[curr] = True
	order.append(str(curr))
	for i in d[curr]:
		if visited[i]:
			continue
		heappush(q, i)
print(' '.join(order))


from heapq import *
(n, m) = map(int, input().split())
E = []
for i in range(n):
	E.append([])
for i in range(m):
	(a, b) = map(int, input().split())
	a = a - 1
	b = b - 1
	E[a].append(b)
	E[b].append(a)
ans = []
ard = set()
ins = [0]
while ins:
	u = heappop(ins)
	if u not in ard:
		ans.append(u)
		ard.add(u)
		for j in E[u]:
			heappush(ins, j)
for i in ans:
	print(i + 1, end=' ')


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))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
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 google(p):
	print('Case #' + str(p) + ': ', end='')

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

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

@iterative
def dfs(v, visited, st, new):
	new.append(st)
	visited[st] = 1
	for i in v[st]:
		if visited[i] == 0:
			ok = (yield dfs(v, visited, i, new))
	yield True

def solve():
	(n, m) = sep()
	g = [[] for i in range(n)]
	for i in range(m):
		(a, b) = sep()
		a -= 1
		b -= 1
		g[a].append(b)
		g[b].append(a)
	h = []
	heappush(h, 0)
	ans = []
	vis = [False] * n
	vis[0] = True
	while len(h) != 0:
		curr = heappop(h)
		ans.append(curr)
		for i in g[curr]:
			if not vis[i]:
				heappush(h, i)
				vis[i] = True
	print(' '.join((str(ans[i] + 1) for i in range(n))))
testcase(1)


import heapq
from collections import defaultdict

class Graph:

	def __init__(self, n):
		self.graph = defaultdict(list)
		self.priority = [1]
		self.Ans = []
		self.visited = [False] * (n + 1)

	def addEdge(self, fr, to):
		self.graph[fr].append(to)
		self.graph[to].append(fr)

	def solve(self):
		while self.priority:
			current = heapq.heappop(self.priority)
			self.Ans.append(current)
			self.visited[current] = True
			for i in self.graph[current]:
				if self.visited[i] == False:
					heapq.heappush(self.priority, i)
					self.visited[i] = True
		print(*self.Ans)
(n, m) = map(int, input().split())
G = Graph(n)
for i in range(m):
	(a, b) = map(int, input().split())
	G.addEdge(a, b)
G.solve()


from heapq import heappop, heappush
from sys import stdout
from collections import deque, defaultdict
import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
(n, m) = map(int, input().split())
d = [set() for i in range(n + 1)]
heap = []
for i in range(m):
	(u, v) = map(int, input().split())
	d[u].add(v)
	d[v].add(u)
heap.append(1)
visited = [False for i in range(n + 1)]
while len(heap) > 0:
	sl = heappop(heap)
	if not visited[sl]:
		stdout.write(str(sl) + ' ')
		for e in d[sl]:
			heappush(heap, e)
			if e != sl:
				d[e].remove(sl)
		d[sl] = False
		visited[sl] = True


from heapq import heapify, heappush, heappop

def solve():
	(n, m) = [int(x) for x in input().split()]
	adjs = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = [int(x) for x in input().split()]
		a -= 1
		b -= 1
		adjs[a].append(b)
		adjs[b].append(a)
	seq = [1]
	visited = set([0])
	frontier = adjs[0].copy()
	heapify(frontier)
	while frontier:
		node = heappop(frontier)
		if node in visited:
			continue
		seq.append(node + 1)
		visited.add(node)
		for neighbor in adjs[node]:
			if neighbor not in visited:
				heappush(frontier, neighbor)
	print(*seq)
solve()


import math
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 heapq
from collections import defaultdict
(n, m) = map(int, input().split())
s = set()
ans = []
d = defaultdict(list)
for i in range(m):
	(a, b) = map(int, input().split())
	d[a].append(b)
	d[b].append(a)
ans.append(1)
s.add(1)
st = []
e = 1
scur = set()
heapq.heapify(st)
for j in range(n - 1):
	for i in d[e]:
		if i in s or i in scur:
			continue
		heapq.heappush(st, i)
		scur.add(i)
	e = heapq.heappop(st)
	scur.remove(e)
	ans.append(e)
	s.add(e)
print(*ans, sep=' ')


from collections import defaultdict
import heapq
graph = defaultdict(list)
(nodes, edges) = map(int, input().split())
for i in range(edges):
	(vertex1, vertex2) = map(int, input().split())
	graph[vertex1].append(vertex2)
	graph[vertex2].append(vertex1)
start = [1]
visited = set()
answer = []
while start:
	node = heapq.heappop(start)
	if node not in visited:
		visited.add(node)
		answer.append(node)
		for w in graph[node]:
			heapq.heappush(start, w)
print(*answer)