#include <fstream>
#define NMAX 1001

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

struct nod
{
    int vf;
    struct nod* urm;
};
typedef struct nod * Lista;

void citire();
void determin_eulerian();
void dfs(int x);
bool conex();
int gradepare();
int ciclu(int x, Lista& C, Lista& sfC);
void afisare();

Lista C1, C2, sfC1, sfC2, p;
int n, m;
int d[NMAX];//gradul unui vf
bool a[NMAX][NMAX];//matricea de adiacenta
int viz[NMAX];

int main()
{
    citire();
    //caut un vf neizolat
    if(conex() && gradepare())
    {
        fout<<"Graf eulerian";
        determin_eulerian();
        afisare();
    }
    else  fout<<"ne-eulerian";
    return 0;
}

void citire()
{
    int i, x, y;
    fin>>n>>m;
    for(i=1;i<=m; i++)
    {
        fin>>x>>y;
        d[x]++;//numar gradele
        d[y]++;
        a[x][y]=a[y][x]=true;

    }
}

bool conex()
{
    int i, x;
    for(x=1; x<=n && !d[x]; x++)
        if(x>n)
        return 1;
    //i este vf nevizitat
    dfs(x);

    for(i=1; i<=n; i++)
    if(viz[i] && d[i])
        return 0;
    return 1;
}

void dfs(int x)
{
    int i;
   //verific daca G e conex; fac un dfs din nodul 1
    viz[x]=true;
    for(i=1;i<=n;i++)  //parcurg linia lui x
        if(a[x][i] && !viz[i])
           dfs(i);
}


int gradepare()
{
    //verific daca gardele oricarui vf din graf sunt pare
    int i;
    for(i=1;i<=m; i++)
        if(d[i]%2)return 0;
    return 1;
}


void determin_eulerian()
{
    int x, nr2, total;
    Lista p, q;
    //caut n vf cu gradul nenul
    for(x=1; x<=n && !d[x]; x++)
    //x are gradul nenul
    total=ciclu(x,C1,sfC1);//am constr ciclul C1

    while(total<n)
    {
        //caut pe C1 un vf cu gradul nenul
        for(p=C1; !d[p->vf]; p=p->urm)
        //acum p indica un vf cu gradul nenul
        nr2=ciclu(p->vf, C2, sfC2);//am constr ciclul C2

        //reunesc ciclul C1 cu ciclul C2
        q=p->urm;
        p->urm=C2->urm;
        sfC1->urm=q;
        total+=nr2;
    }
}

int ciclu(int x, Lista& C, Lista& sfC)
{
    int y, uvf, lg=0;
    //acum construiesc lista; sfarsitul si inceputul se modifica
    Lista p;
    //incep ciclul cu vf x
    //aloc memorie pt un nod
    p=new nod;
    p->vf=x; p->urm=NULL;
    C=sfC=p;//singurul, primul si ultimul
    do
    {
        //caut un vf adiacent cu ultimul vf din lista
        uvf=sfC->vf;//ultimul nod din lista
        //parcurg linia cu vf pana dau de un y adiacent cu el
        for(y=1; a[uvf][y]; y++)
        //adaug muchia [uvf,y] in ciclul eulerian

        sfC->urm=p; sfC=p;
        lg++;
        a[uvf][y]=a[y][uvf]=false;
        d[y]--;
        d[uvf]--;
    }
    while(y!=x);
    return lg;

}

void afisare()
{
    Lista p;
    for(p=C1; p;p=p->urm)
            fout<<p->vf<<' ';
        fout<<'\n';
}