#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> v;
vector<bool> visit;
int cnt = 0;//cnt != n判断不是连通图
void dfs(int index){
    visit[index] = true;
    cnt++;
    for (int i = 0; i < v[index].size(); i++) {
        if(visit[v[index][i]] == false){
            dfs(v[index][i]);
        }
    }
}
int main(){
    int n, m, a, b, even = 0;
    cin >> n >> m;
    v.resize(n + 1);
    visit.resize(n + 1);
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if(i != 1) cout << " ";
        cout << v[i].size();
        if(v[i].size() % 2 == 0) even++;
    }
    cout << endl;
    dfs(1);
    if(even == n && cnt == n) cout << "Eulerian\n";
    else if(even == n - 2 && cnt == n) cout << "Semi-Eulerian\n";
    else cout << "Non-Eulerian\n";
    return 0;
}