本题请你编写程序,输出给定无向连通图中的欧拉回路。
输入格式:
输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex
(≤20)。
第二行给出两个正整数,依次为当前要创建的图的顶点数 n 和边数 m(保证顶点数至少为 3 且不超过最大顶点数量)。
随后 m 行,每行给出一条无向边的两个端点的编号。顶点编号从 0 开始,编号间以 1 个空格分隔。
题目保证没有边被重复给出,并且图一定是连通的。
输出格式:
如果欧拉回路不存在,在一行中输出 No Euler circuit.
。
如果欧拉回路存在,在一行中按以下格式输出:
0->v1->v2->...->0
其中 v1
、v2
等为欧拉回路途径的顶点编号。注意回路必须从编号为 0 的顶点开始,并以回到编号为 0 的顶点结束。
输入样例 1:
20
12 21
1 3
1 4
2 3
2 8
3 4
3 6
3 7
3 9
4 5
4 7
4 10
4 11
5 10
6 9
7 9
7 10
8 9
9 0
9 10
10 11
10 0
输出样例 1:
0->10->7->9->8->2->3->4->1->3->9->6->3->7->4->5->10->11->4->10->9->0
注意:欧拉回路的输出顺序是不唯一的,以任何顺序输出都可以,有特殊裁判程序判断输出的正确性。例如下列输出也是正确的。
0->9->10->5->4->3->1->4->7->9->8->2->3->6->9->3->7->10->11->4->10->0
输入样例 2:
20
4 5
0 1
1 2
2 3
3 0
2 0
输出样例 2:
No Euler circuit.