//Eulerian Path欧拉路径  Eulerian circuit欧拉回路  vertex顶点
//even degree偶数度  semi-Eulerian半欧拉图  Non-Eulerian非欧拉图
//undirected graph无向图  degree度数

//It has been proven that connected graphs with all vertices of even degree have an Eulerian circuit, and such graphs are called Eulerian.
//已经证明，所有偶数度顶点的连通图都有一个欧拉回路，这样的图被称为欧拉图。

// If there are exactly two vertices of odd degree, all Eulerian paths start at one of them and end at the other.
//如果恰好有两个奇数度的顶点，所有欧拉路径都从其中一个开始，在另一个结束。

//A graph that has an Eulerian path but not an Eulerian circuit is called semi-Eulerian.
//具有欧拉路径但没有欧拉回路的图称为半欧拉图。

//each describes an edge by giving the two ends of the edge (the vertices are numbered from 1 to N)
//每个都通过给出边的两端来描述边（顶点从1到N编号）
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

//欧拉图Eulerian
//1.连通
//2.所有点的度数为偶数

//如果一个连通图中有两个顶点的度数为奇数，那么必然没有欧拉回路

//半欧拉图Semi-Eulerian
//1.连通
//2.2个点度数为奇数，其余的点度数为偶数

//非欧拉图,不属于欧拉图和半欧拉图 Non-Eulerian

//1.判断连通性,遍历图,从某点出发看是否遍历所有点（DFS）
//2.判断点的度数,有几个点度数是奇数,扫描所有点

const int N = 510;
int n,m;
bool g[N][N],st[N];
int d[N];//每个点度数

int dfs(int u)
{
    st[u] = true;

    int res = 1;//先把自己这个点算上
    for(int i = 1; i<=n; i++)
        if(!st[i] && g[u][i]) res += dfs(i);
    return res;
}

int main()
{
    cin>>n>>m;
    for(int i = 0; i<m; i++)
    {
        int a,b;
        cin>>a>>b;
        g[a][b] = g[b][a] = true;
        d[a]++,d[b]++;
    }
    int cnt = dfs(1);

    //所有点的度数输出
    cout<<d[1];
    for(int i = 2; i<=n; i++) cout<<' '<<d[i];
    cout<<endl;
    if(cnt==n)//连通
    {
        //判断一共有多少点的度数是奇数
        int s = 0;
        for(int i = 1; i<=n; i++)
            if(d[i]%2)
                s++;
        if(s==0) puts("Eulerian");
        else if(s==2) puts("Semi-Eulerian");
        else puts("Non-Eulerian");
    }
    else puts("Non-Eulerian");
}