Jenna is playing a computer game involving a large map with $n$ cities numbered sequentially from $1$ to $n$ that are connected by $m$ bidirectional roads. The game's objective is to travel to as many cities as possible without visiting any city more than once. The more cities the player visits, the more points they earn.

As Jenna's fellow student at Hackerland University, she asks you for help choosing an optimal path. Given the map, can you help her find a path that maximizes her score?

Note: She can start and end her path at any two distinct cities.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the number of cities) and $m$ (the number of roads). 

Each line $\boldsymbol{i}$ of the $m$ subsequent lines contains two space-separated integers, $x_i$ and $y_i$, describing a bidirectional road between cities $x_i$ and $y_i$.

Map Generation Algorithm    

The graph representing the map was generated randomly in the following way:

Initially, the graph was empty.
Permutations $p_1,\ldots,p_n$ were chosen uniformly at random among all $n!$ permutations.
For each $i\in\{1,\ldots,n-1\}$, edge $(p_i,p_{i+1})$ was added to the graph.
An additional $m-n+1$ edges were chosen uniformly at random among all possible sets of $m-n+1$ edges which don't intersect with edges added during step $3$.

Constraints

$1\leq n\leq10^4$
$1\leq m\leq10^5$
$1\leq x_i,y_i\leq n$
For $30\%$ of test $n\leq25$ and $m\leq75$.
For $50\%$ of test $n\leq100$ and $m\leq500$.
For $70\%$ of test $n\leq500$ and $m\leq2500$.
It's guaranteed that a valid path of length $n$ always exists. 

Scoring

A valid path of length $\boldsymbol{d}$ earns $(\frac{d}{n})^2\times100\%$ of a test case's available points. The total score will be rounded to next $5\%$.

Output Format

Print the following two lines of output:

The first line must contain a single integer, $\boldsymbol{d}$, denoting the length of the path.
The second line must contain $\boldsymbol{d}$ distinct space-separated integers describing Jenna's path in the same order in which she visited each city.

Sample Input 0
4 5
3 1
3 4
2 4
2 3
4 1

Sample Output 0
4
1 4 2 3

Explanation 0

The diagrams below depict the city's initial map, an optimal path that would earn a full score, and an alternative path that would earn a partial score:

In the optimal path (center image), Jenna walks the path $1\to4\to2\to3$. This answer earns $\textbf{100\%}$ of the maximum score because the path length, $\begin{array}{c}4\end{array}$, is equal to $n$ (i.e., she was able to visit every city exactly once). 

In the alternative path (right image), Jenna walks the path $1\rightarrow4\rightarrow3$ for $(\frac{3}{4})^2\times100\%=\frac{9}{16}\times100\%=56.25\%\Rightarrow60\%$ of the maximum score.

Source: hackerrank | Difficulty: MEDIUM_HARD


Solutions:
from collections import defaultdict
from random import choice

class Graph(object):

	def __init__(self):
		self._connections = defaultdict(set)

	@property
	def connections(self):
		return self._connections

	@connections.setter
	def connections(self, value):
		self._connections = defaultdict(set)
		self._connections.update(value)

	def copy(self, donor):
		graph_copy = type(self)()
		graph_copy.connections = donor.connections
		return graph_copy

	def add_arc(self, source, destination):
		self._connections[source].add(destination)
		self._connections[destination].add(source)

	def remove_node(self, node):
		for connected_node in self._connections[node]:
			self._connections[connected_node].remove(node)
		del self._connections[node]

def choice(nodes, graph):
	nodes = list(nodes)
	best_choice = None
	best_choice_score = float('inf')
	for node in nodes:
		this_node_score = len(graph._connections[node])
		if this_node_score < best_choice_score:
			best_choice_score = this_node_score
			best_choice = node
	return best_choice

def random_walk(graph):
	current_node = choice(graph._connections.keys(), graph)
	path = []
	while True:
		path.append(current_node)
		choices = graph._connections[current_node]
		if not choices:
			break
		graph.remove_node(current_node)
		next_node = choice(choices, graph)
		current_node = next_node
	return path

def read_inputs():
	return input().strip().split()
(number_of_cities, number_of_roads) = map(int, read_inputs())
roads = []
for _ in range(number_of_roads):
	roads.append(read_inputs())
graph = Graph()
for (source, destination) in roads:
	graph.add_arc(source, destination)
path = random_walk(graph)
print(len(path))
print(*path)


from collections import defaultdict
from random import choice

class Graph(object):

	def __init__(self):
		self._connections = defaultdict(set)

	@property
	def connections(self):
		return self._connections

	@connections.setter
	def connections(self, value):
		self._connections = defaultdict(set)
		self._connections.update(value)

	def copy(self, donor):
		graph_copy = type(self)()
		graph_copy.connections = donor.connections
		return graph_copy

	def add_arc(self, source, destination):
		self._connections[source].add(destination)
		self._connections[destination].add(source)

	def remove_node(self, node):
		for connected_node in self._connections[node]:
			self._connections[connected_node].remove(node)
		del self._connections[node]

def choice(nodes, graph):
	nodes = list(nodes)
	best_choice = None
	best_choice_score = float('inf')
	for node in nodes:
		this_node_score = len(graph._connections[node])
		if this_node_score < best_choice_score:
			best_choice_score = this_node_score
			best_choice = node
	return best_choice

def random_walk(graph):
	current_node = choice(graph._connections.keys(), graph)
	path = []
	while True:
		path.append(current_node)
		choices = graph._connections[current_node]
		if not choices:
			break
		graph.remove_node(current_node)
		next_node = choice(choices, graph)
		current_node = next_node
	return path

def read_inputs():
	return input().strip().split()
(number_of_cities, number_of_roads) = map(int, read_inputs())
roads = []
for _ in range(number_of_roads):
	roads.append(read_inputs())
graph = Graph()
for (source, destination) in roads:
	graph.add_arc(source, destination)
path = random_walk(graph)
print(len(path))
print(*path)


def create_map(roads):
	city_map = {}
	for (city1, city2) in roads:
		if city1 in city_map:
			city_map[city1].append(city2)
		else:
			city_map[city1] = [city2]
		if city2 in city_map:
			city_map[city2].append(city1)
		else:
			city_map[city2] = [city1]
	return city_map

def find_longest_path(city_map, not_visited):
	min_roads = total_cities
	current_city = 0
	for city in not_visited:
		cities_connected = len(city_map[city])
		if cities_connected < min_roads:
			current_city = city
			min_roads = cities_connected
	longest_path = [current_city]
	while len(not_visited) > 1:
		next_city = 0
		min_roads = total_cities
		for city in city_map[current_city]:
			cities_connected = len(city_map[city])
			if 1 < cities_connected < min_roads:
				next_city = city
				min_roads = cities_connected
		if next_city == 0:
			if len(city_map[current_city]) > 0:
				longest_path.append(city_map[current_city][-1])
			return longest_path
		else:
			longest_path.append(next_city)
			not_visited.remove(current_city)
			for city in city_map[current_city]:
				city_map[city].remove(current_city)
			current_city = next_city
	return longest_path
roads = []
(total_cities, total_roads) = map(int, input().strip().split(' '))
for road_no in range(total_roads):
	roads.append(list(map(int, input().strip().split(' '))))
if total_roads == 0 and total_cities == 0:
	print(0)
elif total_roads == 0:
	print('1\n1')
else:
	city_map = create_map(roads)
	not_visited = [city for city in city_map]
	longest_path = find_longest_path(city_map, not_visited)
	length = len(longest_path)
	print(length)
	print(' '.join(list(map(str, longest_path))))


graph = {}
(n, m) = input().split()
n = int(n)
m = int(m)
for i in range(m):
	(city1, city2) = input().split()
	if city1 not in graph:
		graph[city1] = []
	graph[city1].append(city2)
	if city2 not in graph:
		graph[city2] = []
	graph[city2].append(city1)
visitedCity = []
visited = True
minCity = 0
minEdge = m
for city in graph:
	if len(graph[city]) < minEdge:
		minEdge = len(graph[city])
		minCity = city
visitedCity.append(minCity)
currentcity = minCity
while visited:
	minCity = 0
	minEdge = m
	visited = False
	for adjcity in graph[currentcity]:
		if len(graph[adjcity]) > 1 and len(graph[adjcity]) < minEdge:
			minEdge = len(graph[adjcity])
			minCity = adjcity
	if minCity != 0:
		visitedCity.append(minCity)
		visited = True
		for i in graph[currentcity]:
			graph[i].remove(currentcity)
	else:
		visitedCity.append(graph[currentcity].pop())
	currentcity = minCity
print(len(visitedCity))
for i in range(len(visitedCity) - 1):
	print(visitedCity[i], end='')
	print(' ', end='')
print(visitedCity[-1])


import random

class graph(object):

	def __init__(self):
		self.graph = {}

	def set_edge(self, i, j):
		if i not in self.graph:
			self.graph[i] = [j]
		if j not in self.graph:
			self.graph[j] = [i]
		if i not in self.graph[j]:
			self.graph[j].append(i)
		if j not in self.graph[i]:
			self.graph[i].append(j)
(n, m) = input().split()
(n, m) = (int(n), int(m))
map_graph = graph()
for a0 in range(m):
	(i, j) = input().split()
	(i, j) = (int(i), int(j))
	map_graph.set_edge(i, j)
paths = []
edges_lens = [(i, len(map_graph.graph[i])) for i in map_graph.graph]
edges_lens.sort(key=lambda x: x[1])
node = edges_lens[0][0]
paths.append(node)
stop = False
while stop != True:
	edges = map_graph.graph[node]
	edges_lens = [(i, len(map_graph.graph[i])) for i in edges]
	edges_lens.sort(key=lambda x: x[1])
	stop = True
	for i in edges_lens:
		if i[0] not in paths:
			for j in map_graph.graph[node]:
				map_graph.graph[j].remove(node)
			node = i[0]
			paths.append(node)
			stop = False
			break
print(len(paths))
for n in paths[:-1]:
	print(n, end=' ')
print(paths[-1])


def readints():
	return [int(s) for s in input().split(' ')]
(n, m) = readints()
adjList = [[] for i in range(n)]
for i in range(m):
	(x, y) = readints()
	adjList[x - 1].append(y - 1)
	adjList[y - 1].append(x - 1)
currentNode = 0
for i in range(n):
	if len(adjList[i]) < len(adjList[currentNode]):
		currentNode = i
result = []
visited = set()
while True:
	result.append(currentNode + 1)
	visited.add(currentNode)
	for i in adjList[currentNode]:
		adjList[i].remove(currentNode)
	nextNode = None
	for i in adjList[currentNode]:
		if i not in visited and (nextNode is None or len(adjList[i]) < len(adjList[nextNode])):
			nextNode = i
	if nextNode is None:
		break
	currentNode = nextNode
print(len(result))
print(' '.join(map(str, result)))


import copy
[n, m] = list(map(int, input().strip().split()))
canGo = [[] for i in range(n)]
for i in range(m):
	[x, y] = list(map(int, input().strip().split()))
	canGo[x - 1].append(y - 1)
	canGo[y - 1].append(x - 1)
maxPath = []
visited = [False for j in range(n)]
childCount = [len(canGo[node]) for node in range(n)]
currentNode = childCount.index(min(childCount))
path = []
while currentNode is not None:
	visited[currentNode] = True
	path.append(currentNode)
	candidate = None
	for node in canGo[currentNode]:
		if not visited[node]:
			if candidate == None or childCount[node] < childCount[candidate]:
				candidate = node
	for node in canGo[currentNode]:
		childCount[node] -= 1
	currentNode = candidate
print(len(path))
print(' '.join(list(map(str, [i + 1 for i in path]))))


def Print(*args):
	pass
(n, m) = map(int, input().split(' '))
c_nbrs = {}
cities_left = set()
for _ in range(m):
	(c1, c2) = input().split(' ')
	nbrs = c_nbrs.get(c1, set())
	nbrs.add(c2)
	c_nbrs[c1] = nbrs
	cities_left.add(c1)
	nbrs = c_nbrs.get(c2, set())
	nbrs.add(c1)
	c_nbrs[c2] = nbrs
	cities_left.add(c2)
path = []
min_nbrs = n
for c in cities_left:
	if len(c_nbrs[c]) < min_nbrs:
		city = c
		min_nbrs = len(c_nbrs[c])
path.append(city)
while len(cities_left) > 1:
	Print(city, path, cities_left)
	min_nbrs = n
	next_city = None
	for nbr in c_nbrs[city]:
		if len(c_nbrs[nbr]) > 1 and len(c_nbrs[nbr]) < min_nbrs:
			next_city = nbr
			min_nbrs = len(c_nbrs[nbr])
	if next_city == None:
		if len(c_nbrs[city]) > 0:
			path.append(c_nbrs[city].pop())
		break
	path.append(next_city)
	Print('remove', city, cities_left)
	cities_left.remove(city)
	for i in c_nbrs[city]:
		c_nbrs[i].remove(city)
	city = next_city
print(len(path))
print(' '.join(map(str, path)))


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


from collections import defaultdict
from random import choice

class Graph(object):

	def __init__(self):
		self._connections = defaultdict(set)

	@property
	def connections(self):
		return self._connections

	@connections.setter
	def connections(self, value):
		self._connections = defaultdict(set)
		self._connections.update(value)

	def copy(self, donor):
		graph_copy = type(self)()
		graph_copy.connections = donor.connections
		return graph_copy

	def add_arc(self, source, destination):
		self._connections[source].add(destination)
		self._connections[destination].add(source)

	def remove_node(self, node):
		for connected_node in self._connections[node]:
			self._connections[connected_node].remove(node)
		del self._connections[node]

def choice(nodes, graph):
	nodes = list(nodes)
	best_choice = None
	best_choice_score = float('inf')
	for node in nodes:
		this_node_score = len(graph._connections[node])
		if this_node_score < best_choice_score:
			best_choice_score = this_node_score
			best_choice = node
	return best_choice

def random_walk(graph):
	current_node = choice(graph._connections.keys(), graph)
	path = []
	while True:
		path.append(current_node)
		choices = graph._connections[current_node]
		if not choices:
			break
		graph.remove_node(current_node)
		next_node = choice(choices, graph)
		current_node = next_node
	return path

def read_inputs():
	return input().strip().split()
(number_of_cities, number_of_roads) = map(int, read_inputs())
roads = []
for _ in range(number_of_roads):
	roads.append(read_inputs())
graph = Graph()
for (source, destination) in roads:
	graph.add_arc(source, destination)
path = random_walk(graph)
print(len(path))
print(*path)


import sys
(n, m) = [int(x) for x in sys.stdin.readline().split()]
edges = {}
for i in range(n):
	edges[i] = set()
for i in range(m):
	(u, v) = [int(x) - 1 for x in sys.stdin.readline().split()]
	edges[u].add(v)
	edges[v].add(u)

def start_vertex():
	ranks = []
	for u in edges.keys():
		ranks.append((len(edges[u]), u))
	ranks = sorted(ranks)
	(count, u) = next(iter(ranks))
	return u

def next_vertex(u, visited):
	ranks = []
	for v in edges[u]:
		if v in visited:
			continue
		count = 0
		for w in edges[v]:
			if w not in visited:
				count += 1
		ranks.append((count, v))
	if len(ranks) == 0:
		return None
	ranks = sorted(ranks)
	for (count, v) in ranks:
		if count != 0:
			return v
	(count, v) = next(iter(ranks))
	return v

def path(u, visited):
	path = [u]
	while True:
		u = path[-1]
		v = next_vertex(u, visited)
		if v is None:
			return path
		visited.add(v)
		path.append(v)

def solve():
	u = start_vertex()
	path_1 = path(u, set([u]))[1:]
	path_2 = path(u, set(path_1))[1:]
	path_1.reverse()
	return path_1 + [u] + path_2
path = solve()
print(len(path))
print(' '.join([str(u + 1) for u in path]))


(c, r) = map(int, input().split())

def dfs(visited, graph, gc, node):
	visited.append(node)
	m = 99999999
	for k in graph[node]:
		graph[k].remove(node)
		gc[k] -= 1
		graph.pop(node, None)
		gc.pop(node, None)
		if gc[k] < m and gc[k] > 1:
			m = gc[k]
			nex = k
		elif gc[k] < m:
			m = gc[k]
			nex = k
	print(graph, gc, nex)
	if gc[nex] == 0:
		visited.append(nex)
	else:
		dfs(visited, graph, gc, nex)
graph = {key: [] for key in [*range(1, c + 1)]}
gc = {key: 0 for key in [*range(1, c + 1)]}
for _ in range(r):
	t = list(map(int, input().split()))
	graph[t[0]] += [t[1]]
	graph[t[1]] += [t[0]]
	gc[t[0]] += 1
	gc[t[1]] += 1
nex = min(gc, key=gc.get)
visited = set()
vis = []
while gc[nex] != 0:
	node = nex
	vis.append(node)
	m = 99999999
	for k in graph[node]:
		graph[k].remove(node)
		gc[k] -= 1
		graph.pop(node, None)
		gc.pop(node, None)
		if gc[k] < m and gc[k] > 1:
			m = gc[k]
			nex = k
		elif gc[k] < m:
			m = gc[k]
			nex = k
	if gc[nex] == 0:
		vis.append(nex)
print(len(vis))
print(' '.join(list(map(str, vis))))


from collections import defaultdict
from random import choice

class Graph(object):

	def __init__(self):
		self._connections = defaultdict(set)

	@property
	def connections(self):
		return self._connections

	@connections.setter
	def connections(self, value):
		self._connections = defaultdict(set)
		self._connections.update(value)

	def copy(self, donor):
		graph_copy = type(self)()
		graph_copy.connections = donor.connections
		return graph_copy

	def add_arc(self, source, destination):
		self._connections[source].add(destination)
		self._connections[destination].add(source)

	def remove_node(self, node):
		for connected_node in self._connections[node]:
			self._connections[connected_node].remove(node)
		del self._connections[node]

def choice(nodes, graph):
	nodes = list(nodes)
	best_choice = None
	best_choice_score = float('inf')
	for node in nodes:
		this_node_score = len(graph._connections[node])
		if this_node_score < best_choice_score:
			best_choice_score = this_node_score
			best_choice = node
	return best_choice

def random_walk(graph):
	current_node = choice(graph._connections.keys(), graph)
	path = []
	while True:
		path.append(current_node)
		choices = graph._connections[current_node]
		if not choices:
			break
		graph.remove_node(current_node)
		next_node = choice(choices, graph)
		current_node = next_node
	return path

def read_inputs():
	return input().strip().split()
(number_of_cities, number_of_roads) = map(int, read_inputs())
roads = []
for _ in range(number_of_roads):
	roads.append(read_inputs())
graph = Graph()
for (source, destination) in roads:
	graph.add_arc(source, destination)
path = random_walk(graph)
print(len(path))
print(*path)


from collections import defaultdict
from random import choice

class Graph(object):

	def __init__(self):
		self._connections = defaultdict(set)

	@property
	def connections(self):
		return self._connections

	@connections.setter
	def connections(self, value):
		self._connections = defaultdict(set)
		self._connections.update(value)

	def copy(self, donor):
		graph_copy = type(self)()
		graph_copy.connections = donor.connections
		return graph_copy

	def add_arc(self, source, destination):
		self._connections[source].add(destination)
		self._connections[destination].add(source)

	def remove_node(self, node):
		for connected_node in self._connections[node]:
			self._connections[connected_node].remove(node)
		del self._connections[node]

def choice(nodes, graph):
	nodes = list(nodes)
	best_choice = None
	best_choice_score = float('inf')
	for node in nodes:
		this_node_score = len(graph._connections[node])
		if this_node_score < best_choice_score:
			best_choice_score = this_node_score
			best_choice = node
	return best_choice

def random_walk(graph):
	current_node = choice(graph._connections.keys(), graph)
	path = []
	while True:
		path.append(current_node)
		choices = graph._connections[current_node]
		if not choices:
			break
		graph.remove_node(current_node)
		next_node = choice(choices, graph)
		current_node = next_node
	return path

def read_inputs():
	return input().strip().split()
(number_of_cities, number_of_roads) = map(int, read_inputs())
roads = []
for _ in range(number_of_roads):
	roads.append(read_inputs())
graph = Graph()
for (source, destination) in roads:
	graph.add_arc(source, destination)
path = random_walk(graph)
print(len(path))
print(*path)


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = input().split(' ')
n = int(n)
m = int(m)
roads = []
d = {}
for i in range(m):
	roads.append(list(map(int, input().split())))
	if roads[i][0] not in d:
		d[roads[i][0]] = {roads[i][1]}
	else:
		d[roads[i][0]].add(roads[i][1])
	if roads[i][1] not in d:
		d[roads[i][1]] = {roads[i][0]}
	else:
		d[roads[i][1]].add(roads[i][0])
(_, start) = min([[len(d[z]), z] for z in d], key=lambda a: a[0])
route = [start]
x = start
for i in range(1, n):
	if len(d[x]) == 0:
		break
	(_, y) = min([[len(d[z]), z] for z in d[x]], key=lambda a: a[0])
	route.append(y)
	if x in d[y]:
		d[y].remove(x)
	x = y
print(len(route))
for r in route:
	print(r, end=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
route = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	route.append(y)
	x = y
print(len(route))
for r in route:
	print(r, end=' ')


(n, m) = input().split(' ')
n = int(n)
m = int(m)
roads = []
d = {}
for i in range(m):
	roads.append(list(map(int, input().split())))
	if roads[i][0] not in d:
		d[roads[i][0]] = {roads[i][1]}
	else:
		d[roads[i][0]].add(roads[i][1])
	if roads[i][1] not in d:
		d[roads[i][1]] = {roads[i][0]}
	else:
		d[roads[i][1]].add(roads[i][0])
(x, _) = min([[z, len(d[z])] for z in d], key=lambda a: a[1])
route = [x]
for i in range(1, n):
	if len(d[x]) == 0:
		break
	(y, _) = min([[z, len(d[z])] for z in d[x]], key=lambda a: a[1])
	route.append(y)
	if x in d[y]:
		d[y].remove(x)
	x = y
print(len(route))
for r in route:
	print(r, end=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
graph = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in graph:
		graph[x] = {y}
	if x in graph:
		graph[x].add(y)
	if not y in graph:
		graph[y] = {x}
	if y in graph:
		graph[y].add(x)
count = [0] * (n + 1)
for x in graph:
	count[x] = len(graph[x])
(_, start) = min([[count[z], z] for z in graph], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(graph[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in graph[x]], key=lambda a: a[0])
	if x in graph[y]:
		graph[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


from collections import defaultdict

def search_longest_path(graph):
	min_roads = float('inf')
	for (city, conneted_cites) in graph.items():
		conneted_roads = len(conneted_cites)
		if conneted_roads < min_roads:
			current_city = city
			min_roads = conneted_roads
	longest_path = [current_city]
	visited = [current_city]
	while len(visited) != len(graph):
		next_city = 0
		min_roads = float('inf')
		for city in graph[current_city]:
			conneted_roads = len(graph[city])
			if 1 < conneted_roads < min_roads:
				next_city = city
				min_roads = conneted_roads
		if next_city == 0:
			if len(graph[current_city]) > 0:
				longest_path.append(graph[current_city][-1])
			return longest_path
		else:
			longest_path.append(next_city)
			visited.append(next_city)
			for city in graph[current_city]:
				graph[city].remove(current_city)
			current_city = next_city
	return longest_path
(t_city, t_load) = map(int, input().strip().split(' '))
graph = defaultdict(list)
for _ in range(t_load):
	(start, end) = map(int, input().strip().split(' '))
	graph[start].append(end)
	graph[end].append(start)
longest_path = search_longest_path(graph)
print(str(len(longest_path)) + '\n' + ' '.join(map(str, longest_path)))


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
path = []
rel = {}
for _ in range(m):
	[__, ___] = list(map(int, input().split()))
	path.append([__, ___])
	if __ in rel:
		rel[__].add(___)
	else:
		rel[__] = {___}
	if ___ in rel:
		rel[___].add(__)
	else:
		rel[___] = {__}
c = [0] * (n + 1)
for _ in rel:
	c[_] = len(rel[_])
(_, st) = min([[c[x], x] for x in rel], key=lambda i: i[0])
route = [st]
i = st
for _ in range(1, n):
	if len(rel[i]) == 0:
		break
	(__, en) = min([[c[x], x] for x in rel[i]], key=lambda i: i[0])
	if i in rel[en]:
		rel[en].remove(i)
	c[en] -= 1
	route.append(en)
	i = en
print(len(route))
print(*route, sep=' ')


(n, m) = map(int, input().split())
roads = []
d = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in d:
		d[x] = {y}
	if x in d:
		d[x].add(y)
	if not y in d:
		d[y] = {x}
	if y in d:
		d[y].add(x)
count = [0] * (n + 1)
for x in d:
	count[x] = len(d[x])
(_, start) = min([[count[z], z] for z in d], key=lambda a: a[0])
way = [start]
x = start
for i in range(1, n):
	if len(d[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in d[x]], key=lambda a: a[0])
	if x in d[y]:
		d[y].remove(x)
	count[y] -= 1
	way.append(y)
	x = y
print(len(way))
print(*way, sep=' ')


(n, m) = map(int, input().split())
roads = []
d = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in d:
		d[x] = {y}
	if x in d:
		d[x].add(y)
	if not y in d:
		d[y] = {x}
	if y in d:
		d[y].add(x)
count = [0] * (n + 1)
for x in d:
	count[x] = len(d[x])
(_, start) = min([[count[z], z] for z in d], key=lambda a: a[0])
way = [start]
x = start
for i in range(1, n):
	if len(d[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in d[x]], key=lambda a: a[0])
	if x in d[y]:
		d[y].remove(x)
	count[y] -= 1
	way.append(y)
	x = y
print(len(way))
print(*way, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(nr_of_cities, nr_of_roads) = map(int, input().split())
roads = []
road_dict = {}
road_counts = [0] * (nr_of_cities + 1)
for i in range(nr_of_roads):
	row = input().split()
	[x, y] = [int(row[0]), int(row[1])]
	roads.append([x, y])
	if x not in road_dict:
		road_dict[x] = {y}
	else:
		road_dict[x].add(y)
	if y not in road_dict:
		road_dict[y] = {x}
	else:
		road_dict[y].add(x)
for x in road_dict:
	road_counts[x] = len(road_dict[x])
(_, start) = min([[road_counts[z], z] for z in road_dict], key=lambda a: a[0])
path = [start]
x = start
i = 1
while True:
	if len(road_dict[x]) == 0 or i == nr_of_cities:
		break
	(_, y) = min([[road_counts[z], z] for z in road_dict[x]], key=lambda a: a[0])
	if x in road_dict[y]:
		road_dict[y].remove(x)
	road_counts[y] -= 1
	path.append(y)
	x = y
	i += 1
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
route = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	route.append(y)
	x = y
print(len(route))
for r in route:
	print(r, end=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	else:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	else:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
answer = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	answer.append(y)
	x = y
print(len(answer))
print(*answer, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


from collections import defaultdict
from random import choice

class Graph(object):

	def __init__(self):
		self._connections = defaultdict(set)

	@property
	def connections(self):
		return self._connections

	@connections.setter
	def connections(self, value):
		self._connections = defaultdict(set)
		self._connections.update(value)

	def copy(self, donor):
		graph_copy = type(self)()
		graph_copy.connections = donor.connections
		return graph_copy

	def add_arc(self, source, destination):
		self._connections[source].add(destination)
		self._connections[destination].add(source)

	def remove_node(self, node):
		for connected_node in self._connections[node]:
			self._connections[connected_node].remove(node)
		del self._connections[node]

def choice(nodes, graph):
	nodes = list(nodes)
	best_choice = None
	best_choice_score = float('inf')
	for node in nodes:
		this_node_score = len(graph._connections[node])
		if this_node_score < best_choice_score:
			best_choice_score = this_node_score
			best_choice = node
	return best_choice

def random_walk(graph):
	current_node = choice(graph._connections.keys(), graph)
	path = []
	while True:
		path.append(current_node)
		choices = graph._connections[current_node]
		if not choices:
			break
		graph.remove_node(current_node)
		next_node = choice(choices, graph)
		current_node = next_node
	return path

def read_inputs():
	return input().strip().split()
(number_of_cities, number_of_roads) = map(int, read_inputs())
roads = []
for _ in range(number_of_roads):
	roads.append(read_inputs())
graph = Graph()
for (source, destination) in roads:
	graph.add_arc(source, destination)
path = random_walk(graph)
print(len(path))
print(*path)


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')


(n, m) = map(int, input().split())
roads = []
dic = {}
for i in range(m):
	[x, y] = list(map(int, input().split()))
	roads.append([x, y])
	if not x in dic:
		dic[x] = {y}
	if x in dic:
		dic[x].add(y)
	if not y in dic:
		dic[y] = {x}
	if y in dic:
		dic[y].add(x)
count = [0] * (n + 1)
for x in dic:
	count[x] = len(dic[x])
(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])
path = [start]
x = start
for i in range(1, n):
	if len(dic[x]) == 0:
		break
	(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])
	if x in dic[y]:
		dic[y].remove(x)
	count[y] -= 1
	path.append(y)
	x = y
print(len(path))
print(*path, sep=' ')