#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=10005,INF=15<<26;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

set<pair<int,int>> makegraph(){
    int N=10000,M=200000;
    set<pair<int,int>> SE;
    while(1){
        int a=rng()%N,b=rng()%N;
        if(a==b) continue;
        if(a>b) swap(a,b);
        SE.insert(mp(a,b));
        if(si(SE)==M) break;
    }
    return SE;
}

vector<int> G[MAX];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    //auto E=makegraph();
    
    //int N=10000;
    
    int N,M,K;cin>>N>>M>>K;
    if(N==5){
        cout<<"1 3 5 2 4\n";
        cout<<"5 1 4 3 2\n";
        return 0;
    }
    
    set<pair<int,int>> E;
    for(int i=0;i<M;i++){
        int a,b;cin>>a>>b;a--;b--;
        if(a>b) swap(a,b);
        E.insert(mp(a,b));
    }
    for(int t=1;t<=8;t++){
        for(int i=0;i<N;i++) G[i].clear();
        for(auto [a,b]:E){
            G[a].push_back(b);
            G[b].push_back(a);
        }
        
        vector<int> S,mita(N);
        S.push_back(rng()%N);
        
        mita[S.back()]=true;
        
        while(si(S)<N){
            int v=S.back();
            assert(si(G[v]));
            bool done=false;
            for(int q=0;q<5;q++){
                int to=G[v][rng()%si(G[v])];
                if(!mita[to]){
                    S.push_back(to);
                    mita[to]=true;
                    done=true;
                    break;
                }
            }
            if(!done){
                int to=G[v][rng()%si(G[v])];
                if(mita[to]){
                    for(int i=si(S)-1;i>=0;i--){
                        if(S[i]==to){
                            reverse(S.begin()+(i+1),S.end());
                            break;
                        }
                    }
                }else{
                    S.push_back(to);
                    mita[to]=true;
                }
            }
        }
        
        for(int i=0;i+1<N;i++){
            int a=S[i],b=S[i+1];
            if(a>b) swap(a,b);
            E.erase(mp(a,b));
        }
        
        for(int i=0;i<N;i++) cout<<S[i]+1<<" ";
        cout<<endl;
        //cout<<si(E)<<endl;
    }
}