//欧拉图：1：连通 2：所有点的度数为偶数
//半欧拉图：1：连通 2：2个点的度数为奇数其余为偶数
//非欧拉图：以外

#include<iostream>
#include<cstring>

using namespace std;

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) cout<<"Eulerian"<<endl;
        else if(s==2) cout<<"Semi-Eulerian"<<endl;
        else cout<<"Non-Eulerian"<<endl;
    }
    else cout<<"Non-Eulerian"<<endl;

    return 0;
}