题目描述

在图论中，欧拉路径是图中的一条路径，该路径满足恰好访问每个边一次。而欧拉回路是一条在同一顶点处开始和结束的欧拉路径。它们最早由欧拉于 1736 年解决著名的哥尼斯堡七桥问题时提出。事实证明，如果一个连通图的所有顶点的度数都为偶数，那么这个连通图具有欧拉回路，且这个图被称为欧拉图。如果一个连通图中有两个顶点的度数为奇数，其他顶点的度数为偶数，那么所有欧拉路径都从其中一个度数为奇数的顶点开始，并在另一个度数为奇数的顶点结束。具有欧拉路径但不具有欧拉回路的图被称为半欧拉图。现在，给定一个无向图，请你判断它是欧拉图、半欧拉图还是非欧拉图。题目保证给出的数据图是连通的。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示无向图的点和边的数量 ( $1 \le N \le 500$，$1 \le M \le 2000$ )。

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

所有点的编号从 $1 \sim N$。

输出格式

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

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

样例

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

2 4 4 4 4 4 2
Eulerian