#893. 欧拉路径

欧拉路径

题目描述

在图论中,欧拉路径是图中的一条路径,该路径满足恰好访问每个边一次。

而欧拉回路是一条在同一顶点处开始和结束的欧拉路径。

它们最早由欧拉于 1736 年解决著名的哥尼斯堡七桥问题时提出。

事实证明,如果一个连通图的所有顶点的度数都为偶数,那么这个连通图具有欧拉回路,且这个图被称为欧拉图。

如果一个连通图中有两个顶点的度数为奇数,其他顶点的度数为偶数,那么所有欧拉路径都从其中一个度数为奇数的顶点开始,并在另一个度数为奇数的顶点结束。

具有欧拉路径但不具有欧拉回路的图被称为半欧拉图。

现在,给定一个无向图,请你判断它是欧拉图、半欧拉图还是非欧拉图。

输入格式

第一行包含两个整数 NM,表示无向图的点和边的数量。

接下来 M 行,每行包含两个整数 a,b表示点 ab 之间存在一条边。

所有点的编号从 1N

输出格式

首先,在第一行按顺序输出点 1N中每个点的度数。

第二行输出对该图的判断,Eulerian(欧拉图),Semi-Eulerian(半欧拉图),Non-Eulerian(非欧拉图)。

行尾不得有多余空格。

数据范围

1N5001≤N≤500,

1MN(N1)21≤M≤\frac{N(N−1)}{2}

输入样例1:

7 12
5 7
1 2
1 3
2 3
2 4
3 4
5 2
7 6
6 3
4 5
6 4
5 6

输出样例1:

2 4 4 4 4 4 2
Eulerian

输入样例2:

6 10
1 2
1 3
2 3
2 4
3 4
5 2
6 3
4 5
6 4
5 6

输出样例2:

2 4 4 4 3 3
Semi-Eulerian

输入样例3:

5 8
1 2
2 5
5 4
4 1
1 3
3 2
3 4
5 3

输出样例3:

3 3 4 3 3
Non-Eulerian