U237541 判断是否存在欧拉路径

欧拉图 对于无向图 所有点的度数为偶数的连通图有欧拉回路 有且仅有2个点的度为奇数的连通图有欧拉路 欧拉路径定义： 图中经过所有边恰好一次的路径叫欧拉路径（也就是一笔画）。如果此路径的起点和终点相同，则称其为一条欧拉回路。 2.2. 欧拉路径判定（是否存在）： 有向图欧拉路径：图中恰好存在 11 个点出度比入度多 11（这个点即为 起点 SS），11 个点入度比出度多 11（这个点即为 终点 TT），其余节点出度=入度。 有向图欧拉回路：所有点的入度=出度（起点 SS 和终点 TT 可以为任意点）。 无向图欧拉路径：图中恰好存在 22 个点的度数是奇数，其余节点的度数为偶数，这两个度数为奇数的点即为欧拉路径的 起点 SS 和 终点 TT。 无向图欧拉回路：所有点的度数都是偶数（起点 SS 和终点 TT 可以为任意点）。 注：存在欧拉回路（即满足存在欧拉回路的条件），也一定存在欧拉路径。 当然，一副图有欧拉路径，还必须满足将它的有向边视为无向边后它是连通的（不考虑度为 00 的孤立点），连通性的判断我们可以使用并查集或 dfs 等。 3.3. 寻找欧拉路径（默认存在）： 首先根据题意以及判定先确定起点 SS。 从起点 SS 开始 dfs 。 dfs 伪代码如下： 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≤N≤500$, $1≤M≤\frac{N(N−1)}{2}$