AtCoder Grand Contest 017 - Zigzag

source: atcoder

time_limit: 4.0 seconds

memory_limit: 256.0 megabytes

raw_problem:
配点 : <var>1600</var> 点

問題文

下図のように，<var>1</var> 辺が <var>N</var> 個の点からなる正三角形状に，<var>N(N+1)/2</var> 個の点が並んでいます．
上から <var>i</var> 段目の左から <var>j</var> 番目の点を <var>(i, j)</var> で表すことにします(<var>1 \leq i \leq N</var>, <var>1 \leq j \leq i</var>)．
また，<var>(i+1, j)</var> を <var>(i, j)</var> のすぐ左下の点，<var>(i+1, j+1)</var> を <var>(i, j)</var> のすぐ右下の点と呼ぶことにします．

高橋君は，この点を結んで，<var>M</var> 個の折れ線 <var>1, 2, ..., M</var> を描くことにしました．
各折れ線は，<var>(1, 1)</var> から始めて，「現在いる点のすぐ左下の点かすぐ右下の点を選び，現在いる点と選んだ点を直線で結んだのち，選んだ点へ移動する」
ことを <var>N-1</var> 回繰り返すことで得られます．
すなわち，ある <var>X_{i,1}, ..., X_{i,N}</var> が存在して，次が成り立ちます：

折れ線 <var>i</var> は，<var>N</var> 個の点 <var>(1, X_{i,1}), (2, X_{i,2}), ..., (N, X_{i,N})</var> をこの順で結んでいる．

<var>j=1, 2, ..., N-1</var> に対して，<var>X_{i,j+1} = X_{i,j}</var> または <var>X_{i,j+1} = X_{i,j}+1</var> が成り立つ．

高橋君は，折れ線 <var>i+1</var> が折れ線 <var>i</var> の左に来ることはないように折れ線を描きたいです．
つまり，<var>j=1, 2, ..., N</var> に対して，<var>X_{1,j} \leq X_{2,j} \leq ... \leq X_{M,j}</var> が成り立ちます．

また，高橋君は，折れ線の曲がり方について <var>K</var> 個の条件を満たすように折れ線を描かなければなりません．
<var>i</var> 番目の条件は <var>(A_i, B_i, C_i)</var> で表され，これは次を意味します：

<var>C_i=0</var> のときは，折れ線 <var>A_i</var> を描くとき，<var>B_i</var> 回目の移動においては，その時いる点のすぐ左下の点を選ぶ．

<var>C_i=1</var> のときは，折れ線 <var>A_i</var> を描くとき，<var>B_i</var> 回目の移動においては，その時いる点のすぐ右下の点を選ぶ．

すなわち，<var>X_{A_i, {B_i}+1} = X_{A_i, B_i} + C_i</var> を意味します．

高橋君が <var>M</var> 個の折れ線を描く方法が何通りあるかを mod <var>1000000007</var> で求めてください．

注意

提出を行う前に，「コードテスト」を利用して実行時間を計測することを強く推奨する．

制約

<var>1 \leq N \leq 20</var>

<var>1 \leq M \leq 20</var>

<var>0 \leq K \leq (N-1)M</var>

<var>1 \leq A_i \leq M</var>

<var>1 \leq B_i \leq N-1</var>

<var>C_i = 0,1</var>

<var>(A_i, B_i)</var> として同じ組は複数回与えられない．

入力

入力は以下の形式で標準入力から与えられる。

<var>N</var> <var>M</var> <var>K</var>
<var>A_1</var> <var>B_1</var> <var>C_1</var>
<var>A_2</var> <var>B_2</var> <var>C_2</var>
:
<var>A_K</var> <var>B_K</var> <var>C_K</var>

出力

高橋君が <var>M</var> 個の折れ線を描く方法は何通りあるかを mod <var>1000000007</var> で出力せよ．

入力例 1

3 2 1
1 2 0

出力例 1

6

下図に示すように，<var>6</var> 通りの描き方があります．ただし，赤線は折れ線 <var>1</var>，緑線は折れ線 <var>2</var> を表します：

入力例 2

3 2 2
1 1 1
2 1 0

出力例 2

0

入力例 3

5 4 2
1 3 1
4 2 0

出力例 3

172

入力例 4

20 20 0

出力例 4

881396682

Score : <var>1600</var> points

Problem Statement

There are <var>N(N+1)/2</var> dots arranged to form an equilateral triangle whose sides consist of <var>N</var> dots, as shown below.
The <var>j</var>-th dot from the left in the <var>i</var>-th row from the top is denoted by <var>(i, j)</var> (<var>1 \leq i \leq N</var>, <var>1 \leq j \leq i</var>).
Also, we will call <var>(i+1, j)</var> immediately lower-left to <var>(i, j)</var>, and <var>(i+1, j+1)</var> immediately lower-right to <var>(i, j)</var>.

Takahashi is drawing <var>M</var> polygonal lines <var>L_1, L_2, ..., L_M</var> by connecting these dots.
Each <var>L_i</var> starts at <var>(1, 1)</var>, and visits the dot that is immediately lower-left or lower-right to the current dots <var>N-1</var> times.
More formally, there exist <var>X_{i,1}, ..., X_{i,N}</var> such that:

<var>L_i</var> connects the <var>N</var> points <var>(1, X_{i,1}), (2, X_{i,2}), ..., (N, X_{i,N})</var>, in this order.

For each <var>j=1, 2, ..., N-1</var>, either <var>X_{i,j+1} = X_{i,j}</var> or <var>X_{i,j+1} = X_{i,j}+1</var> holds.

Takahashi would like to draw these lines so that no part of <var>L_{i+1}</var> is to the left of <var>L_{i}</var>.
That is, for each <var>j=1, 2, ..., N</var>, <var>X_{1,j} \leq X_{2,j} \leq ... \leq X_{M,j}</var> must hold.

Additionally, there are <var>K</var> conditions on the shape of the lines that must be followed.
The <var>i</var>-th condition is denoted by <var>(A_i, B_i, C_i)</var>, which means:

If <var>C_i=0</var>, <var>L_{A_i}</var> must visit the immediately lower-left dot for the <var>B_i</var>-th move.

If <var>C_i=1</var>, <var>L_{A_i}</var> must visit the immediately lower-right dot for the <var>B_i</var>-th move.

That is, <var>X_{A_i, {B_i}+1} = X_{A_i, B_i} + C_i</var> must hold.

In how many ways can Takahashi draw <var>M</var> polygonal lines? Find the count modulo <var>1000000007</var>.

Notes

Before submission, it is strongly recommended to measure the execution time of your code using "Custom Test".

Constraints

<var>1 \leq N \leq 20</var>

<var>1 \leq M \leq 20</var>

<var>0 \leq K \leq (N-1)M</var>

<var>1 \leq A_i \leq M</var>

<var>1 \leq B_i \leq N-1</var>

<var>C_i = 0</var> or <var>1</var>

No pair appears more than once as <var>(A_i, B_i)</var>.

Input

Input is given from Standard Input in the following format:

<var>N</var> <var>M</var> <var>K</var>
<var>A_1</var> <var>B_1</var> <var>C_1</var>
<var>A_2</var> <var>B_2</var> <var>C_2</var>
:
<var>A_K</var> <var>B_K</var> <var>C_K</var>

Output

Print the number of ways for Takahashi to draw <var>M</var> polygonal lines, modulo <var>1000000007</var>.

Sample Input 1

3 2 1
1 2 0

Sample Output 1

6

There are six ways to draw lines, as shown below. Here, red lines represent <var>L_1</var>, and green lines represent <var>L_2</var>.

Sample Input 2

3 2 2
1 1 1
2 1 0

Sample Output 2

0

Sample Input 3

5 4 2
1 3 1
4 2 0

Sample Output 3

172

Sample Input 4

20 20 0

Sample Output 4

881396682

question:
There are $N(N+1)/2$ dots arranged to form an equilateral triangle whose sides consist of $N$ dots, as shown below.
The $j$-th dot from the left in the $i$-th row from the top is denoted by $(i, j)$ ($1 \leq i \leq N$, $1 \leq j \leq i$).
Also, we will call $(i+1, j)$ immediately lower-left to $(i, j)$, and $(i+1, j+1)$ immediately lower-right to $(i, j)$.
![image](1.png)
Takahashi is drawing $M$ polygonal lines $L_1, L_2, ..., L_M$ by connecting these dots.
Each $L_i$ starts at $(1, 1)$, and visits the dot that is immediately lower-left or lower-right to the current dots $N-1$ times.
More formally, there exist $X_{i,1}, ..., X_{i,N}$ such that:

- $L_i$ connects the $N$ points $(1, X_{i,1}), (2, X_{i,2}), ..., (N, X_{i,N})$, in this order.
- For each $j=1, 2, ..., N-1$, either $X_{i,j+1} = X_{i,j}$ or $X_{i,j+1} = X_{i,j}+1$ holds.

Takahashi would like to draw these lines so that no part of $L_{i+1}$ is to the left of $L_{i}$.
That is, for each $j=1, 2, ..., N$, $X_{1,j} \leq X_{2,j} \leq ... \leq X_{M,j}$ must hold.
Additionally, there are $K$ conditions on the shape of the lines that must be followed.
The $i$-th condition is denoted by $(A_i, B_i, C_i)$, which means:

- If $C_i=0$, $L_{A_i}$ must visit the immediately lower-left dot for the $B_i$-th move.
- If $C_i=1$, $L_{A_i}$ must visit the immediately lower-right dot for the $B_i$-th move.

That is, $X_{A_i, {B_i}+1} = X_{A_i, B_i} + C_i$ must hold.
In how many ways can Takahashi draw $M$ polygonal lines? Find the count modulo $1000000007$.

Notes
Before submission, it is strongly recommended to measure the execution time of your code using "Custom Test".

Constraints

- $1 \leq N \leq 20$
- $1 \leq M \leq 20$
- $0 \leq K \leq (N-1)M$
- $1 \leq A_i \leq M$
- $1 \leq B_i \leq N-1$
- $C_i = 0$ or $1$
- No pair appears more than once as $(A_i, B_i)$.

Input
Input is given from Standard Input in the following format:
$N$ $M$ $K$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$
:

$A_K$ $B_K$ $C_K$

Output
Print the number of ways for Takahashi to draw $M$ polygonal lines, modulo $1000000007$.

Sample Input 1
3 2 1
1 2 0

Sample Output 1
6

There are six ways to draw lines, as shown below. Here, red lines represent $L_1$, and green lines represent $L_2$.
![image](2.png)

Sample Input 2
3 2 2
1 1 1
2 1 0

Sample Output 2
0

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

Sample Output 3
172

Sample Input 4
20 20 0

Sample Output 4
881396682

image_tags: Tree Tree

data_split: test


solutions: ["from collections import defaultdict\nfrom random import choice\n\nclass Graph(object):\n\n\tdef __init__(self):\n\t\tself._connections = defaultdict(set)\n\n\t@property\n\tdef connections(self):\n\t\treturn self._connections\n\n\t@connections.setter\n\tdef connections(self, value):\n\t\tself._connections = defaultdict(set)\n\t\tself._connections.update(value)\n\n\tdef copy(self, donor):\n\t\tgraph_copy = type(self)()\n\t\tgraph_copy.connections = donor.connections\n\t\treturn graph_copy\n\n\tdef add_arc(self, source, destination):\n\t\tself._connections[source].add(destination)\n\t\tself._connections[destination].add(source)\n\n\tdef remove_node(self, node):\n\t\tfor connected_node in self._connections[node]:\n\t\t\tself._connections[connected_node].remove(node)\n\t\tdel self._connections[node]\n\ndef choice(nodes, graph):\n\tnodes = list(nodes)\n\tbest_choice = None\n\tbest_choice_score = float('inf')\n\tfor node in nodes:\n\t\tthis_node_score = len(graph._connections[node])\n\t\tif this_node_score < best_choice_score:\n\t\t\tbest_choice_score = this_node_score\n\t\t\tbest_choice = node\n\treturn best_choice\n\ndef random_walk(graph):\n\tcurrent_node = choice(graph._connections.keys(), graph)\n\tpath = []\n\twhile True:\n\t\tpath.append(current_node)\n\t\tchoices = graph._connections[current_node]\n\t\tif not choices:\n\t\t\tbreak\n\t\tgraph.remove_node(current_node)\n\t\tnext_node = choice(choices, graph)\n\t\tcurrent_node = next_node\n\treturn path\n\ndef read_inputs():\n\treturn input().strip().split()\n(number_of_cities, number_of_roads) = map(int, read_inputs())\nroads = []\nfor _ in range(number_of_roads):\n\troads.append(read_inputs())\ngraph = Graph()\nfor (source, destination) in roads:\n\tgraph.add_arc(source, destination)\npath = random_walk(graph)\nprint(len(path))\nprint(*path)\n", "from collections import defaultdict\nfrom random import choice\n\nclass Graph(object):\n\n\tdef __init__(self):\n\t\tself._connections = defaultdict(set)\n\n\t@property\n\tdef connections(self):\n\t\treturn self._connections\n\n\t@connections.setter\n\tdef connections(self, value):\n\t\tself._connections = defaultdict(set)\n\t\tself._connections.update(value)\n\n\tdef copy(self, donor):\n\t\tgraph_copy = type(self)()\n\t\tgraph_copy.connections = donor.connections\n\t\treturn graph_copy\n\n\tdef add_arc(self, source, destination):\n\t\tself._connections[source].add(destination)\n\t\tself._connections[destination].add(source)\n\n\tdef remove_node(self, node):\n\t\tfor connected_node in self._connections[node]:\n\t\t\tself._connections[connected_node].remove(node)\n\t\tdel self._connections[node]\n\ndef choice(nodes, graph):\n\tnodes = list(nodes)\n\tbest_choice = None\n\tbest_choice_score = float('inf')\n\tfor node in nodes:\n\t\tthis_node_score = len(graph._connections[node])\n\t\tif this_node_score < best_choice_score:\n\t\t\tbest_choice_score = this_node_score\n\t\t\tbest_choice = node\n\treturn best_choice\n\ndef random_walk(graph):\n\tcurrent_node = choice(graph._connections.keys(), graph)\n\tpath = []\n\twhile True:\n\t\tpath.append(current_node)\n\t\tchoices = graph._connections[current_node]\n\t\tif not choices:\n\t\t\tbreak\n\t\tgraph.remove_node(current_node)\n\t\tnext_node = choice(choices, graph)\n\t\tcurrent_node = next_node\n\treturn path\n\ndef read_inputs():\n\treturn input().strip().split()\n(number_of_cities, number_of_roads) = map(int, read_inputs())\nroads = []\nfor _ in range(number_of_roads):\n\troads.append(read_inputs())\ngraph = Graph()\nfor (source, destination) in roads:\n\tgraph.add_arc(source, destination)\npath = random_walk(graph)\nprint(len(path))\nprint(*path)\n", "def create_map(roads):\n\tcity_map = {}\n\tfor (city1, city2) in roads:\n\t\tif city1 in city_map:\n\t\t\tcity_map[city1].append(city2)\n\t\telse:\n\t\t\tcity_map[city1] = [city2]\n\t\tif city2 in city_map:\n\t\t\tcity_map[city2].append(city1)\n\t\telse:\n\t\t\tcity_map[city2] = [city1]\n\treturn city_map\n\ndef find_longest_path(city_map, not_visited):\n\tmin_roads = total_cities\n\tcurrent_city = 0\n\tfor city in not_visited:\n\t\tcities_connected = len(city_map[city])\n\t\tif cities_connected < min_roads:\n\t\t\tcurrent_city = city\n\t\t\tmin_roads = cities_connected\n\tlongest_path = [current_city]\n\twhile len(not_visited) > 1:\n\t\tnext_city = 0\n\t\tmin_roads = total_cities\n\t\tfor city in city_map[current_city]:\n\t\t\tcities_connected = len(city_map[city])\n\t\t\tif 1 < cities_connected < min_roads:\n\t\t\t\tnext_city = city\n\t\t\t\tmin_roads = cities_connected\n\t\tif next_city == 0:\n\t\t\tif len(city_map[current_city]) > 0:\n\t\t\t\tlongest_path.append(city_map[current_city][-1])\n\t\t\treturn longest_path\n\t\telse:\n\t\t\tlongest_path.append(next_city)\n\t\t\tnot_visited.remove(current_city)\n\t\t\tfor city in city_map[current_city]:\n\t\t\t\tcity_map[city].remove(current_city)\n\t\t\tcurrent_city = next_city\n\treturn longest_path\nroads = []\n(total_cities, total_roads) = map(int, input().strip().split(' '))\nfor road_no in range(total_roads):\n\troads.append(list(map(int, input().strip().split(' '))))\nif total_roads == 0 and total_cities == 0:\n\tprint(0)\nelif total_roads == 0:\n\tprint('1\\n1')\nelse:\n\tcity_map = create_map(roads)\n\tnot_visited = [city for city in city_map]\n\tlongest_path = find_longest_path(city_map, not_visited)\n\tlength = len(longest_path)\n\tprint(length)\n\tprint(' '.join(list(map(str, longest_path))))\n", "graph = {}\n(n, m) = input().split()\nn = int(n)\nm = int(m)\nfor i in range(m):\n\t(city1, city2) = input().split()\n\tif city1 not in graph:\n\t\tgraph[city1] = []\n\tgraph[city1].append(city2)\n\tif city2 not in graph:\n\t\tgraph[city2] = []\n\tgraph[city2].append(city1)\nvisitedCity = []\nvisited = True\nminCity = 0\nminEdge = m\nfor city in graph:\n\tif len(graph[city]) < minEdge:\n\t\tminEdge = len(graph[city])\n\t\tminCity = city\nvisitedCity.append(minCity)\ncurrentcity = minCity\nwhile visited:\n\tminCity = 0\n\tminEdge = m\n\tvisited = False\n\tfor adjcity in graph[currentcity]:\n\t\tif len(graph[adjcity]) > 1 and len(graph[adjcity]) < minEdge:\n\t\t\tminEdge = len(graph[adjcity])\n\t\t\tminCity = adjcity\n\tif minCity != 0:\n\t\tvisitedCity.append(minCity)\n\t\tvisited = True\n\t\tfor i in graph[currentcity]:\n\t\t\tgraph[i].remove(currentcity)\n\telse:\n\t\tvisitedCity.append(graph[currentcity].pop())\n\tcurrentcity = minCity\nprint(len(visitedCity))\nfor i in range(len(visitedCity) - 1):\n\tprint(visitedCity[i], end='')\n\tprint(' ', end='')\nprint(visitedCity[-1])\n", "import random\n\nclass graph(object):\n\n\tdef __init__(self):\n\t\tself.graph = {}\n\n\tdef set_edge(self, i, j):\n\t\tif i not in self.graph:\n\t\t\tself.graph[i] = [j]\n\t\tif j not in self.graph:\n\t\t\tself.graph[j] = [i]\n\t\tif i not in self.graph[j]:\n\t\t\tself.graph[j].append(i)\n\t\tif j not in self.graph[i]:\n\t\t\tself.graph[i].append(j)\n(n, m) = input().split()\n(n, m) = (int(n), int(m))\nmap_graph = graph()\nfor a0 in range(m):\n\t(i, j) = input().split()\n\t(i, j) = (int(i), int(j))\n\tmap_graph.set_edge(i, j)\npaths = []\nedges_lens = [(i, len(map_graph.graph[i])) for i in map_graph.graph]\nedges_lens.sort(key=lambda x: x[1])\nnode = edges_lens[0][0]\npaths.append(node)\nstop = False\nwhile stop != True:\n\tedges = map_graph.graph[node]\n\tedges_lens = [(i, len(map_graph.graph[i])) for i in edges]\n\tedges_lens.sort(key=lambda x: x[1])\n\tstop = True\n\tfor i in edges_lens:\n\t\tif i[0] not in paths:\n\t\t\tfor j in map_graph.graph[node]:\n\t\t\t\tmap_graph.graph[j].remove(node)\n\t\t\tnode = i[0]\n\t\t\tpaths.append(node)\n\t\t\tstop = False\n\t\t\tbreak\nprint(len(paths))\nfor n in paths[:-1]:\n\tprint(n, end=' ')\nprint(paths[-1])\n", "def readints():\n\treturn [int(s) for s in input().split(' ')]\n(n, m) = readints()\nadjList = [[] for i in range(n)]\nfor i in range(m):\n\t(x, y) = readints()\n\tadjList[x - 1].append(y - 1)\n\tadjList[y - 1].append(x - 1)\ncurrentNode = 0\nfor i in range(n):\n\tif len(adjList[i]) < len(adjList[currentNode]):\n\t\tcurrentNode = i\nresult = []\nvisited = set()\nwhile True:\n\tresult.append(currentNode + 1)\n\tvisited.add(currentNode)\n\tfor i in adjList[currentNode]:\n\t\tadjList[i].remove(currentNode)\n\tnextNode = None\n\tfor i in adjList[currentNode]:\n\t\tif i not in visited and (nextNode is None or len(adjList[i]) < len(adjList[nextNode])):\n\t\t\tnextNode = i\n\tif nextNode is None:\n\t\tbreak\n\tcurrentNode = nextNode\nprint(len(result))\nprint(' '.join(map(str, result)))\n", "import copy\n[n, m] = list(map(int, input().strip().split()))\ncanGo = [[] for i in range(n)]\nfor i in range(m):\n\t[x, y] = list(map(int, input().strip().split()))\n\tcanGo[x - 1].append(y - 1)\n\tcanGo[y - 1].append(x - 1)\nmaxPath = []\nvisited = [False for j in range(n)]\nchildCount = [len(canGo[node]) for node in range(n)]\ncurrentNode = childCount.index(min(childCount))\npath = []\nwhile currentNode is not None:\n\tvisited[currentNode] = True\n\tpath.append(currentNode)\n\tcandidate = None\n\tfor node in canGo[currentNode]:\n\t\tif not visited[node]:\n\t\t\tif candidate == None or childCount[node] < childCount[candidate]:\n\t\t\t\tcandidate = node\n\tfor node in canGo[currentNode]:\n\t\tchildCount[node] -= 1\n\tcurrentNode = candidate\nprint(len(path))\nprint(' '.join(list(map(str, [i + 1 for i in path]))))\n", "def Print(*args):\n\tpass\n(n, m) = map(int, input().split(' '))\nc_nbrs = {}\ncities_left = set()\nfor _ in range(m):\n\t(c1, c2) = input().split(' ')\n\tnbrs = c_nbrs.get(c1, set())\n\tnbrs.add(c2)\n\tc_nbrs[c1] = nbrs\n\tcities_left.add(c1)\n\tnbrs = c_nbrs.get(c2, set())\n\tnbrs.add(c1)\n\tc_nbrs[c2] = nbrs\n\tcities_left.add(c2)\npath = []\nmin_nbrs = n\nfor c in cities_left:\n\tif len(c_nbrs[c]) < min_nbrs:\n\t\tcity = c\n\t\tmin_nbrs = len(c_nbrs[c])\npath.append(city)\nwhile len(cities_left) > 1:\n\tPrint(city, path, cities_left)\n\tmin_nbrs = n\n\tnext_city = None\n\tfor nbr in c_nbrs[city]:\n\t\tif len(c_nbrs[nbr]) > 1 and len(c_nbrs[nbr]) < min_nbrs:\n\t\t\tnext_city = nbr\n\t\t\tmin_nbrs = len(c_nbrs[nbr])\n\tif next_city == None:\n\t\tif len(c_nbrs[city]) > 0:\n\t\t\tpath.append(c_nbrs[city].pop())\n\t\tbreak\n\tpath.append(next_city)\n\tPrint('remove', city, cities_left)\n\tcities_left.remove(city)\n\tfor i in c_nbrs[city]:\n\t\tc_nbrs[i].remove(city)\n\tcity = next_city\nprint(len(path))\nprint(' '.join(map(str, path)))\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "from collections import defaultdict\nfrom random import choice\n\nclass Graph(object):\n\n\tdef __init__(self):\n\t\tself._connections = defaultdict(set)\n\n\t@property\n\tdef connections(self):\n\t\treturn self._connections\n\n\t@connections.setter\n\tdef connections(self, value):\n\t\tself._connections = defaultdict(set)\n\t\tself._connections.update(value)\n\n\tdef copy(self, donor):\n\t\tgraph_copy = type(self)()\n\t\tgraph_copy.connections = donor.connections\n\t\treturn graph_copy\n\n\tdef add_arc(self, source, destination):\n\t\tself._connections[source].add(destination)\n\t\tself._connections[destination].add(source)\n\n\tdef remove_node(self, node):\n\t\tfor connected_node in self._connections[node]:\n\t\t\tself._connections[connected_node].remove(node)\n\t\tdel self._connections[node]\n\ndef choice(nodes, graph):\n\tnodes = list(nodes)\n\tbest_choice = None\n\tbest_choice_score = float('inf')\n\tfor node in nodes:\n\t\tthis_node_score = len(graph._connections[node])\n\t\tif this_node_score < best_choice_score:\n\t\t\tbest_choice_score = this_node_score\n\t\t\tbest_choice = node\n\treturn best_choice\n\ndef random_walk(graph):\n\tcurrent_node = choice(graph._connections.keys(), graph)\n\tpath = []\n\twhile True:\n\t\tpath.append(current_node)\n\t\tchoices = graph._connections[current_node]\n\t\tif not choices:\n\t\t\tbreak\n\t\tgraph.remove_node(current_node)\n\t\tnext_node = choice(choices, graph)\n\t\tcurrent_node = next_node\n\treturn path\n\ndef read_inputs():\n\treturn input().strip().split()\n(number_of_cities, number_of_roads) = map(int, read_inputs())\nroads = []\nfor _ in range(number_of_roads):\n\troads.append(read_inputs())\ngraph = Graph()\nfor (source, destination) in roads:\n\tgraph.add_arc(source, destination)\npath = random_walk(graph)\nprint(len(path))\nprint(*path)\n", "import sys\n(n, m) = [int(x) for x in sys.stdin.readline().split()]\nedges = {}\nfor i in range(n):\n\tedges[i] = set()\nfor i in range(m):\n\t(u, v) = [int(x) - 1 for x in sys.stdin.readline().split()]\n\tedges[u].add(v)\n\tedges[v].add(u)\n\ndef start_vertex():\n\tranks = []\n\tfor u in edges.keys():\n\t\tranks.append((len(edges[u]), u))\n\tranks = sorted(ranks)\n\t(count, u) = next(iter(ranks))\n\treturn u\n\ndef next_vertex(u, visited):\n\tranks = []\n\tfor v in edges[u]:\n\t\tif v in visited:\n\t\t\tcontinue\n\t\tcount = 0\n\t\tfor w in edges[v]:\n\t\t\tif w not in visited:\n\t\t\t\tcount += 1\n\t\tranks.append((count, v))\n\tif len(ranks) == 0:\n\t\treturn None\n\tranks = sorted(ranks)\n\tfor (count, v) in ranks:\n\t\tif count != 0:\n\t\t\treturn v\n\t(count, v) = next(iter(ranks))\n\treturn v\n\ndef path(u, visited):\n\tpath = [u]\n\twhile True:\n\t\tu = path[-1]\n\t\tv = next_vertex(u, visited)\n\t\tif v is None:\n\t\t\treturn path\n\t\tvisited.add(v)\n\t\tpath.append(v)\n\ndef solve():\n\tu = start_vertex()\n\tpath_1 = path(u, set([u]))[1:]\n\tpath_2 = path(u, set(path_1))[1:]\n\tpath_1.reverse()\n\treturn path_1 + [u] + path_2\npath = solve()\nprint(len(path))\nprint(' '.join([str(u + 1) for u in path]))\n", "(c, r) = map(int, input().split())\n\ndef dfs(visited, graph, gc, node):\n\tvisited.append(node)\n\tm = 99999999\n\tfor k in graph[node]:\n\t\tgraph[k].remove(node)\n\t\tgc[k] -= 1\n\t\tgraph.pop(node, None)\n\t\tgc.pop(node, None)\n\t\tif gc[k] < m and gc[k] > 1:\n\t\t\tm = gc[k]\n\t\t\tnex = k\n\t\telif gc[k] < m:\n\t\t\tm = gc[k]\n\t\t\tnex = k\n\tprint(graph, gc, nex)\n\tif gc[nex] == 0:\n\t\tvisited.append(nex)\n\telse:\n\t\tdfs(visited, graph, gc, nex)\ngraph = {key: [] for key in [*range(1, c + 1)]}\ngc = {key: 0 for key in [*range(1, c + 1)]}\nfor _ in range(r):\n\tt = list(map(int, input().split()))\n\tgraph[t[0]] += [t[1]]\n\tgraph[t[1]] += [t[0]]\n\tgc[t[0]] += 1\n\tgc[t[1]] += 1\nnex = min(gc, key=gc.get)\nvisited = set()\nvis = []\nwhile gc[nex] != 0:\n\tnode = nex\n\tvis.append(node)\n\tm = 99999999\n\tfor k in graph[node]:\n\t\tgraph[k].remove(node)\n\t\tgc[k] -= 1\n\t\tgraph.pop(node, None)\n\t\tgc.pop(node, None)\n\t\tif gc[k] < m and gc[k] > 1:\n\t\t\tm = gc[k]\n\t\t\tnex = k\n\t\telif gc[k] < m:\n\t\t\tm = gc[k]\n\t\t\tnex = k\n\tif gc[nex] == 0:\n\t\tvis.append(nex)\nprint(len(vis))\nprint(' '.join(list(map(str, vis))))\n", "from collections import defaultdict\nfrom random import choice\n\nclass Graph(object):\n\n\tdef __init__(self):\n\t\tself._connections = defaultdict(set)\n\n\t@property\n\tdef connections(self):\n\t\treturn self._connections\n\n\t@connections.setter\n\tdef connections(self, value):\n\t\tself._connections = defaultdict(set)\n\t\tself._connections.update(value)\n\n\tdef copy(self, donor):\n\t\tgraph_copy = type(self)()\n\t\tgraph_copy.connections = donor.connections\n\t\treturn graph_copy\n\n\tdef add_arc(self, source, destination):\n\t\tself._connections[source].add(destination)\n\t\tself._connections[destination].add(source)\n\n\tdef remove_node(self, node):\n\t\tfor connected_node in self._connections[node]:\n\t\t\tself._connections[connected_node].remove(node)\n\t\tdel self._connections[node]\n\ndef choice(nodes, graph):\n\tnodes = list(nodes)\n\tbest_choice = None\n\tbest_choice_score = float('inf')\n\tfor node in nodes:\n\t\tthis_node_score = len(graph._connections[node])\n\t\tif this_node_score < best_choice_score:\n\t\t\tbest_choice_score = this_node_score\n\t\t\tbest_choice = node\n\treturn best_choice\n\ndef random_walk(graph):\n\tcurrent_node = choice(graph._connections.keys(), graph)\n\tpath = []\n\twhile True:\n\t\tpath.append(current_node)\n\t\tchoices = graph._connections[current_node]\n\t\tif not choices:\n\t\t\tbreak\n\t\tgraph.remove_node(current_node)\n\t\tnext_node = choice(choices, graph)\n\t\tcurrent_node = next_node\n\treturn path\n\ndef read_inputs():\n\treturn input().strip().split()\n(number_of_cities, number_of_roads) = map(int, read_inputs())\nroads = []\nfor _ in range(number_of_roads):\n\troads.append(read_inputs())\ngraph = Graph()\nfor (source, destination) in roads:\n\tgraph.add_arc(source, destination)\npath = random_walk(graph)\nprint(len(path))\nprint(*path)\n", "from collections import defaultdict\nfrom random import choice\n\nclass Graph(object):\n\n\tdef __init__(self):\n\t\tself._connections = defaultdict(set)\n\n\t@property\n\tdef connections(self):\n\t\treturn self._connections\n\n\t@connections.setter\n\tdef connections(self, value):\n\t\tself._connections = defaultdict(set)\n\t\tself._connections.update(value)\n\n\tdef copy(self, donor):\n\t\tgraph_copy = type(self)()\n\t\tgraph_copy.connections = donor.connections\n\t\treturn graph_copy\n\n\tdef add_arc(self, source, destination):\n\t\tself._connections[source].add(destination)\n\t\tself._connections[destination].add(source)\n\n\tdef remove_node(self, node):\n\t\tfor connected_node in self._connections[node]:\n\t\t\tself._connections[connected_node].remove(node)\n\t\tdel self._connections[node]\n\ndef choice(nodes, graph):\n\tnodes = list(nodes)\n\tbest_choice = None\n\tbest_choice_score = float('inf')\n\tfor node in nodes:\n\t\tthis_node_score = len(graph._connections[node])\n\t\tif this_node_score < best_choice_score:\n\t\t\tbest_choice_score = this_node_score\n\t\t\tbest_choice = node\n\treturn best_choice\n\ndef random_walk(graph):\n\tcurrent_node = choice(graph._connections.keys(), graph)\n\tpath = []\n\twhile True:\n\t\tpath.append(current_node)\n\t\tchoices = graph._connections[current_node]\n\t\tif not choices:\n\t\t\tbreak\n\t\tgraph.remove_node(current_node)\n\t\tnext_node = choice(choices, graph)\n\t\tcurrent_node = next_node\n\treturn path\n\ndef read_inputs():\n\treturn input().strip().split()\n(number_of_cities, number_of_roads) = map(int, read_inputs())\nroads = []\nfor _ in range(number_of_roads):\n\troads.append(read_inputs())\ngraph = Graph()\nfor (source, destination) in roads:\n\tgraph.add_arc(source, destination)\npath = random_walk(graph)\nprint(len(path))\nprint(*path)\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = input().split(' ')\nn = int(n)\nm = int(m)\nroads = []\nd = {}\nfor i in range(m):\n\troads.append(list(map(int, input().split())))\n\tif roads[i][0] not in d:\n\t\td[roads[i][0]] = {roads[i][1]}\n\telse:\n\t\td[roads[i][0]].add(roads[i][1])\n\tif roads[i][1] not in d:\n\t\td[roads[i][1]] = {roads[i][0]}\n\telse:\n\t\td[roads[i][1]].add(roads[i][0])\n(_, start) = min([[len(d[z]), z] for z in d], key=lambda a: a[0])\nroute = [start]\nx = start\nfor i in range(1, n):\n\tif len(d[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[len(d[z]), z] for z in d[x]], key=lambda a: a[0])\n\troute.append(y)\n\tif x in d[y]:\n\t\td[y].remove(x)\n\tx = y\nprint(len(route))\nfor r in route:\n\tprint(r, end=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\nroute = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\troute.append(y)\n\tx = y\nprint(len(route))\nfor r in route:\n\tprint(r, end=' ')\n", "(n, m) = input().split(' ')\nn = int(n)\nm = int(m)\nroads = []\nd = {}\nfor i in range(m):\n\troads.append(list(map(int, input().split())))\n\tif roads[i][0] not in d:\n\t\td[roads[i][0]] = {roads[i][1]}\n\telse:\n\t\td[roads[i][0]].add(roads[i][1])\n\tif roads[i][1] not in d:\n\t\td[roads[i][1]] = {roads[i][0]}\n\telse:\n\t\td[roads[i][1]].add(roads[i][0])\n(x, _) = min([[z, len(d[z])] for z in d], key=lambda a: a[1])\nroute = [x]\nfor i in range(1, n):\n\tif len(d[x]) == 0:\n\t\tbreak\n\t(y, _) = min([[z, len(d[z])] for z in d[x]], key=lambda a: a[1])\n\troute.append(y)\n\tif x in d[y]:\n\t\td[y].remove(x)\n\tx = y\nprint(len(route))\nfor r in route:\n\tprint(r, end=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ngraph = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in graph:\n\t\tgraph[x] = {y}\n\tif x in graph:\n\t\tgraph[x].add(y)\n\tif not y in graph:\n\t\tgraph[y] = {x}\n\tif y in graph:\n\t\tgraph[y].add(x)\ncount = [0] * (n + 1)\nfor x in graph:\n\tcount[x] = len(graph[x])\n(_, start) = min([[count[z], z] for z in graph], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(graph[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in graph[x]], key=lambda a: a[0])\n\tif x in graph[y]:\n\t\tgraph[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "from collections import defaultdict\n\ndef search_longest_path(graph):\n\tmin_roads = float('inf')\n\tfor (city, conneted_cites) in graph.items():\n\t\tconneted_roads = len(conneted_cites)\n\t\tif conneted_roads < min_roads:\n\t\t\tcurrent_city = city\n\t\t\tmin_roads = conneted_roads\n\tlongest_path = [current_city]\n\tvisited = [current_city]\n\twhile len(visited) != len(graph):\n\t\tnext_city = 0\n\t\tmin_roads = float('inf')\n\t\tfor city in graph[current_city]:\n\t\t\tconneted_roads = len(graph[city])\n\t\t\tif 1 < conneted_roads < min_roads:\n\t\t\t\tnext_city = city\n\t\t\t\tmin_roads = conneted_roads\n\t\tif next_city == 0:\n\t\t\tif len(graph[current_city]) > 0:\n\t\t\t\tlongest_path.append(graph[current_city][-1])\n\t\t\treturn longest_path\n\t\telse:\n\t\t\tlongest_path.append(next_city)\n\t\t\tvisited.append(next_city)\n\t\t\tfor city in graph[current_city]:\n\t\t\t\tgraph[city].remove(current_city)\n\t\t\tcurrent_city = next_city\n\treturn longest_path\n(t_city, t_load) = map(int, input().strip().split(' '))\ngraph = defaultdict(list)\nfor _ in range(t_load):\n\t(start, end) = map(int, input().strip().split(' '))\n\tgraph[start].append(end)\n\tgraph[end].append(start)\nlongest_path = search_longest_path(graph)\nprint(str(len(longest_path)) + '\\n' + ' '.join(map(str, longest_path)))\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\npath = []\nrel = {}\nfor _ in range(m):\n\t[__, ___] = list(map(int, input().split()))\n\tpath.append([__, ___])\n\tif __ in rel:\n\t\trel[__].add(___)\n\telse:\n\t\trel[__] = {___}\n\tif ___ in rel:\n\t\trel[___].add(__)\n\telse:\n\t\trel[___] = {__}\nc = [0] * (n + 1)\nfor _ in rel:\n\tc[_] = len(rel[_])\n(_, st) = min([[c[x], x] for x in rel], key=lambda i: i[0])\nroute = [st]\ni = st\nfor _ in range(1, n):\n\tif len(rel[i]) == 0:\n\t\tbreak\n\t(__, en) = min([[c[x], x] for x in rel[i]], key=lambda i: i[0])\n\tif i in rel[en]:\n\t\trel[en].remove(i)\n\tc[en] -= 1\n\troute.append(en)\n\ti = en\nprint(len(route))\nprint(*route, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\nd = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in d:\n\t\td[x] = {y}\n\tif x in d:\n\t\td[x].add(y)\n\tif not y in d:\n\t\td[y] = {x}\n\tif y in d:\n\t\td[y].add(x)\ncount = [0] * (n + 1)\nfor x in d:\n\tcount[x] = len(d[x])\n(_, start) = min([[count[z], z] for z in d], key=lambda a: a[0])\nway = [start]\nx = start\nfor i in range(1, n):\n\tif len(d[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in d[x]], key=lambda a: a[0])\n\tif x in d[y]:\n\t\td[y].remove(x)\n\tcount[y] -= 1\n\tway.append(y)\n\tx = y\nprint(len(way))\nprint(*way, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\nd = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in d:\n\t\td[x] = {y}\n\tif x in d:\n\t\td[x].add(y)\n\tif not y in d:\n\t\td[y] = {x}\n\tif y in d:\n\t\td[y].add(x)\ncount = [0] * (n + 1)\nfor x in d:\n\tcount[x] = len(d[x])\n(_, start) = min([[count[z], z] for z in d], key=lambda a: a[0])\nway = [start]\nx = start\nfor i in range(1, n):\n\tif len(d[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in d[x]], key=lambda a: a[0])\n\tif x in d[y]:\n\t\td[y].remove(x)\n\tcount[y] -= 1\n\tway.append(y)\n\tx = y\nprint(len(way))\nprint(*way, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(nr_of_cities, nr_of_roads) = map(int, input().split())\nroads = []\nroad_dict = {}\nroad_counts = [0] * (nr_of_cities + 1)\nfor i in range(nr_of_roads):\n\trow = input().split()\n\t[x, y] = [int(row[0]), int(row[1])]\n\troads.append([x, y])\n\tif x not in road_dict:\n\t\troad_dict[x] = {y}\n\telse:\n\t\troad_dict[x].add(y)\n\tif y not in road_dict:\n\t\troad_dict[y] = {x}\n\telse:\n\t\troad_dict[y].add(x)\nfor x in road_dict:\n\troad_counts[x] = len(road_dict[x])\n(_, start) = min([[road_counts[z], z] for z in road_dict], key=lambda a: a[0])\npath = [start]\nx = start\ni = 1\nwhile True:\n\tif len(road_dict[x]) == 0 or i == nr_of_cities:\n\t\tbreak\n\t(_, y) = min([[road_counts[z], z] for z in road_dict[x]], key=lambda a: a[0])\n\tif x in road_dict[y]:\n\t\troad_dict[y].remove(x)\n\troad_counts[y] -= 1\n\tpath.append(y)\n\tx = y\n\ti += 1\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\nroute = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\troute.append(y)\n\tx = y\nprint(len(route))\nfor r in route:\n\tprint(r, end=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\telse:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\telse:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\nanswer = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tanswer.append(y)\n\tx = y\nprint(len(answer))\nprint(*answer, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "from collections import defaultdict\nfrom random import choice\n\nclass Graph(object):\n\n\tdef __init__(self):\n\t\tself._connections = defaultdict(set)\n\n\t@property\n\tdef connections(self):\n\t\treturn self._connections\n\n\t@connections.setter\n\tdef connections(self, value):\n\t\tself._connections = defaultdict(set)\n\t\tself._connections.update(value)\n\n\tdef copy(self, donor):\n\t\tgraph_copy = type(self)()\n\t\tgraph_copy.connections = donor.connections\n\t\treturn graph_copy\n\n\tdef add_arc(self, source, destination):\n\t\tself._connections[source].add(destination)\n\t\tself._connections[destination].add(source)\n\n\tdef remove_node(self, node):\n\t\tfor connected_node in self._connections[node]:\n\t\t\tself._connections[connected_node].remove(node)\n\t\tdel self._connections[node]\n\ndef choice(nodes, graph):\n\tnodes = list(nodes)\n\tbest_choice = None\n\tbest_choice_score = float('inf')\n\tfor node in nodes:\n\t\tthis_node_score = len(graph._connections[node])\n\t\tif this_node_score < best_choice_score:\n\t\t\tbest_choice_score = this_node_score\n\t\t\tbest_choice = node\n\treturn best_choice\n\ndef random_walk(graph):\n\tcurrent_node = choice(graph._connections.keys(), graph)\n\tpath = []\n\twhile True:\n\t\tpath.append(current_node)\n\t\tchoices = graph._connections[current_node]\n\t\tif not choices:\n\t\t\tbreak\n\t\tgraph.remove_node(current_node)\n\t\tnext_node = choice(choices, graph)\n\t\tcurrent_node = next_node\n\treturn path\n\ndef read_inputs():\n\treturn input().strip().split()\n(number_of_cities, number_of_roads) = map(int, read_inputs())\nroads = []\nfor _ in range(number_of_roads):\n\troads.append(read_inputs())\ngraph = Graph()\nfor (source, destination) in roads:\n\tgraph.add_arc(source, destination)\npath = random_walk(graph)\nprint(len(path))\nprint(*path)\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n", "(n, m) = map(int, input().split())\nroads = []\ndic = {}\nfor i in range(m):\n\t[x, y] = list(map(int, input().split()))\n\troads.append([x, y])\n\tif not x in dic:\n\t\tdic[x] = {y}\n\tif x in dic:\n\t\tdic[x].add(y)\n\tif not y in dic:\n\t\tdic[y] = {x}\n\tif y in dic:\n\t\tdic[y].add(x)\ncount = [0] * (n + 1)\nfor x in dic:\n\tcount[x] = len(dic[x])\n(_, start) = min([[count[z], z] for z in dic], key=lambda a: a[0])\npath = [start]\nx = start\nfor i in range(1, n):\n\tif len(dic[x]) == 0:\n\t\tbreak\n\t(_, y) = min([[count[z], z] for z in dic[x]], key=lambda a: a[0])\n\tif x in dic[y]:\n\t\tdic[y].remove(x)\n\tcount[y] -= 1\n\tpath.append(y)\n\tx = y\nprint(len(path))\nprint(*path, sep=' ')\n"]

source: hacker rank

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

![image](1.png)
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.

data_split: test