/**
 * @file   1126.cpp
 * @author Shuang Hu <hsmath@ubuntu>
 * @date   Thu Jun  3 03:37:50 2021
 * 
 * @brief  PAT 1126:Judge a graph have Eulerian Path or not.
 * 
 * 
 */
#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;
int main(){
    bool ifconnected=true;
    int nodenum;
    int edgenum;
    cin>>nodenum>>edgenum;
    map<int,int> degrees;
    vector<bool> traversed;
    int odddegree=0;
    for(int i=0;i<edgenum;i++){
	int a,b;
	cin>>a>>b;
	degrees[a]++;
	degrees[b]++;
    }
    cout<<degrees[1];
    if(degrees[1]%2){
	odddegree++;
    }
    for(int i=2;i<=nodenum;i++){
	cout<<" "<<degrees[i];
	if(degrees[i]%2){
	    odddegree++;
	}
    }
    cout<<endl;
    traversed.resize(nodenum);
    queue<int> Que;
    Que.push(0);
    while(Que.empty()==false){
	int d=Que.front();
	Que.pop();
	
    }
    if(odddegree==0){
	cout<<"Eulerian"<<endl;
    }else if(odddegree==2){
	cout<<"Semi-Eulerian"<<endl;
    }else{
	cout<<"Non-Eulerian"<<endl;
    }
    return 0;
}