#include<bits/stdc++.h>
using namespace std;
inline int read(){int s=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();return s*f;}
const int N=3e5+10;
int n,m,p1[N]/*有边的前一段*/,p0[N]/*没边的后一段*/,c1,c0;
vector<int> G[N];
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        G[u].push_back(v),G[v].push_back(u);
    }
    for(int i=1;i<=n;++i)sort(G[i].begin(),G[i].end());/*方便二分*/
    for(int i=n;i;--i/*先将两个p数组反着来 方便添加点*/){
        if(!c1){p1[++c1]=i;continue;}/*第一个必须是1*/
        if(!c0){p0[++c0]=i;continue;}
        int u0=p0[c0],u1=p1[c1];
        int pos=lower_bound(G[u1].begin(),G[u1].end(),i)-G[u1].begin();
        if(pos<G[u1].size()&&G[u1][pos]==i){p1[++c1]=i;continue;}
        pos=lower_bound(G[u0].begin(),G[u0].end(),i)-G[u0].begin();
        if(pos>=G[u0].size()||(pos<G[u0].size()&&G[u0][pos]!=i)){p0[++c0]=i;continue;}
        pos=lower_bound(G[u1].begin(),G[u1].end(),u0)-G[u1].begin();
        cout<<i<<" "<<pos<<" "<<G[u0].size()<<" "<<c1<<" "<<c0<<"\n";
        if(pos<G[u1].size()&&G[u1][pos]==u0)--c0,p1[++c1]=u0,p1[++c1]=i;/*用u0将u1和i连接起来*/
        else --c1,p0[++c0]=u1,p0[++c0]=i;/*将u0和i隔开*/
    }
    reverse(p1+1,p1+1+c1),reverse(p0+1,p0+1+c0);
    if(p0[1]==1)swap(p0,p1),swap(c0,c1);
    for(int i=1;i<=c1;++i)printf("%d ",p1[i]);
    for(int i=1;i<=c0;++i)printf("%d ",p0[i]);
    return 0;
}