题目背景

欧拉图

对于无向图

• 所有点的度数为偶数的连通图有欧拉回路

• 有且仅有2个点的度为奇数的连通图有欧拉路径

欧拉路径定义：

图中经过所有边恰好一次的路径叫欧拉路径（也就是一笔画）。如果此路径的起点和终点相同，则称其为一条欧拉回路。

欧拉路径判定（是否存在）：

• 有向图欧拉路径：图中恰好存在 1 个点出度比入度多 1（这个点即为 起点 S），1 个点入度比出度多 1（这个点即为 终点 T），其余节点出度=入度。

• 有向图欧拉回路：所有点的入度=出度（起点 S 和终点 T 可以为任意点）。

• 无向图欧拉路径：图中恰好存在 2 个点的度数是奇数，其余节点的度数为偶数，这两个度数为奇数的点即为欧拉路径的 起点 S 和 终点 T。

• 无向图欧拉回路：所有点的度数都是偶数（起点 S 和终点 T 可以为任意点）。

注：存在欧拉回路（即满足存在欧拉回路的条件），也一定存在欧拉路径。

当然，一副图有欧拉路径，还必须满足将它的有向边视为无向边后它是连通的（不考虑度为 0 的孤立点），连通性的判断我们可以使用并查集或 dfs 等。

寻找欧拉路径（默认存在）：

首先根据题意以及判定先确定起点 S。从起点 S 开始 dfs 。dfs 伪代码如下：

cpp
void dfs(int now)
{
	枚举now的出边。
		如果该边还未被访问
			标记为已访问
			dfs(该边连向的另一个点)
	now入栈
}

最后倒序输出栈内的所有节点即可。

题目描述

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

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

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

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

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

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

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

输入格式

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

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

所有点的编号从 1∼N。

输出格式

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

第二行输出对该图的判断，Eulerian（欧拉图），Semi-Eulerian（半欧拉图），Non-Eulerian（非欧拉图）。

行尾不得有多余空格。

输入输出样例 #1

输入 #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

输入 #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

输入 #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

说明/提示

$1≤N≤500$,

$1≤M≤\frac{N(N−1)}{2}$