#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
int a[100][100],n;
void BF (int start, int *&t, int *&d)
{
    int i,x,*viz=new int [n+1];
    t=new int [n+1];
    d=new int [n+1];
for (i=1;i<=n;i++)
t[i]=0;
    for (i=1; i<=n; i++)
        viz[i]=0;
    queue <int> Q;
    Q.push(start);
    viz[start]=1;
    t[start]=0;
    d[start]=0;

    while (!Q.empty())
    {
        x=Q.front();
        Q.pop();
        cout<<x<<" ";
        for (i=1; i<=n; i++)
        {
            if ((a[x][i])&&(!viz[i]))
              {

                Q.push(i);
            viz[i]=1;
            t[i]=x;
            d[i]=d[x]+1;}
        }
    }
}


int main()
{
   int *v,l,maximv=0,c=0;
    int i,j,k,m,start,x;
    int *t,*d,*b;
    ifstream f("intrare.txt");
    f>>n>>m;

 v=new int [n+1];
 b=new int [n+1];
for(l=1;l<=n;l++)
    v[l]=0;
for(l=1;l<=m;l++)
     {f>>i>>j;
     v[i]++;
     v[j]++;
     a[i][j]=1;
     a[j][i]=1;

    }

for(l=1;l<=n;l++)
    cout<<l<<" ";cout<<endl;
for(l=1;l<=n;l++)
    cout<<v[l]<<" ";





    cout<<"start=";
    cin>>start;
    BF(start,t,d);
    cout<<endl;
    for (i=1; i<=n; i++)
        cout<<t[i]<<" ";
        cout<<endl;
/*for(l=1;l<=n;l++)
    {if(maximv<v[l])
       {maximv=v[l];
       x=l;}}
t[x]=0;
for(i=1;i<=n;i++)
{if(v[i]==1 && t[i]!=0)
 {cout<<t[i]<<" ";
 t[i]=0;}}

 for(i=1;i<=n;i++)
{if(t[i]!=0)
    cout<<t[i]<<" ";}*/
k=1;
for(i=1;i<=n;i++)
{int ok=0;
    if(v[i]==1 && t[i]!=0)
    {b[k]=t[i];
    k++;
v[t[i]]--;
v[i]--;
t[i]=0;
ok=1;
}
if(ok==1)
    i=1;
}
if(n%2==0)
 for(i=1;i<k;i++)
    cout<<b[i]<<" ";
else
for(i=1;i<k;i++)
    cout<<b[i]<<" ";
return 0;
}