#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;
        }
        if(viz[x]==0 && viz[y]!=0){
            viz[x]=1;
            vecini[x]=vecini[y];
        }
        if(viz[y]==0){
                viz[y]=1;
            }
        vecini[y]=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++;
        }
    }
    std::cout<<nr;
    return 0;
}