#include <iostream>
#include <fstream>
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int main(){
    int n,m,x,y,nr=0;
    fin>>n>>m;
    int viz[100001]={0},vecini[100001]={0};
    while(m){
        fin>>x>>y;
        if(viz[x]==0 && viz[y]==0){
            nr++;
            viz[x]=1;
            vecini[x]=nr;
            viz[y]=1;
            vecini[y]=nr;
        }
        if(viz[x]==0 && viz[y]!=0){
            viz[x]=1;
            vecini[x]=vecini[y];
        }
        if(viz[x]!=0 && viz[y]==0){
                viz[y]=1;
                vecini[y]=vecini[x];
            }
        if(viz[x]!=0 && viz[y]!=0 && vecini[x]!=vecini[y])
        {
            // for(int i=1;i<=n;i++){
            //     if(vecini[i]==vecini[y]){
            //         vecini[i]=vecini[x];
            //     }
            // }
            vecini[y]=vecini[x];
            nr--;
        }
        m--;
    }
    for(int i=1;i<=n;i++){
        std::cout<<viz[i]<<" ";
    }
    std::cout<<std::endl;
    for(int i=1;i<=n;i++){
        std::cout<<vecini[i]<<" ";
    }
    for(int i=1;i<=n;i++){
        if(viz[i]==0){
            nr++;
        }
    }
    fout<<nr;   
    return 0;
}