import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class eMain implements Runnable {
    StringTokenizer st;
    BufferedReader in;
    PrintWriter out;

    ArrayList<Integer>[] graph;
    ArrayList<Integer> answ;


    int n,m;
    int num;
    int time=0;
	int pr[];
	int counter=0;
	int anscol[];
	int aa[];
	int bb[];
	int enter[];
	int colors[];
	int leave[];
	int low[];
	int art[];
   	int nums[];
    public static void main(String[] args) {
        new Thread(new eMain()).run();
    }

    public void run() {
        try {
            in = new BufferedReader(new FileReader("biconv.in"));
            out = new PrintWriter(new FileWriter("biconv.out"));
            solve();
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            out.flush();
            out.close();
        }
    }

    String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

    int nextInt() throws NumberFormatException, IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws NumberFormatException, IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(nextToken());
    }

    int min (int a, int b) {
    	if (a<=b) {
    		return a;
    	} else {
    		return b;
    	}
    }
    void DFSVISIT(int a) {

    	int kids = 0;
    	   colors[a] = 1;
    	   low[a]=enter[a]=++time;

    	   int s=graph[a].size();
    	   for (int i=0; i<s; i++){
    		   int ii=aa[graph[a].get(i)];
    		   if(colors[ii]==0) {
    			    pr[ii]=a;
    			    DFSVISIT(ii);
    			    low[a]=min(low[a],low[ii]);

    			    if ((pr[a]!=-1)&&(low[ii]>=enter[a])) {
    			    	art[a]=1;
    			    }
    			    kids++;
    		   } else if((colors[ii]== 1) && (ii!=pr[a])) {
    			   low[a] = min(low[a],enter[ii]);
    		   }

    	   }
    	   if (pr[a]==-1){
    		   if (kids>=2) {
    		   		art[a]=1;

    		   } else {
    			   art[a]=0;
    		   }
    	   }
    	   colors[a]=2;
    	   leave[a]=++time;


    }
    void DFS() {
    	for	(int i=0; i<n; i++) {

    		if (colors[i]==0){

    			DFSVISIT(i);
    		}
    	}
    }
    void DFSVISIT2(int a,int b){
    	colors[a]=1;

    	int s=graph[a].size();

    	for (int i=0; i<s; i++){
    			int ii=aa[graph[a].get(i)];
    			if (colors[ii]==1){
    				anscol[graph[a].get(i)%m]=b;
    				anscol[graph[a].get(i)]=b;
    				if (art[ii]==1) {
        				counter++;
        			}
    			}


    	}
    	for (int i=0; i<s; i++){
			int ii=aa[graph[a].get(i)];

			if (colors[ii]==0){
				anscol[graph[a].get(i)%m]=counter;
				anscol[graph[a].get(i)]=counter;
				DFSVISIT2(ii,counter);

			}


    	}
    	colors[a]=2;


    }

    @SuppressWarnings("unchecked")
	void solve() throws NumberFormatException, IOException {



		n=nextInt();
		m=nextInt();
		answ = new ArrayList();

		colors=new int[n];
		pr=new int[n];
		low=new int[n];
		enter=new int[n];
		leave=new int[n];
		art=new int[n];
		nums=new int[n];
		anscol=new int[2*m];
		aa=new int[2*m];
		bb=new int[2*m];
		for (int i=0; i<n; i++) {
			pr[i]=-1;
			art[i]=0;
		}
		graph=new ArrayList[n];
		for(int i = 0; i < n; i++) {
			graph[i] = new ArrayList<Integer>();

		}
		for (int i=0; i<m; i++) {
			int a, b;
			a=nextInt();
			b=nextInt();
			graph[a-1].add(i);
			graph[b-1].add(i+m);
			aa[i]=b-1;
			aa[i+m]=a-1;
		}
		DFS();
		for (int i=0; i<n;i++) {
			colors[i]=0;
		}
		for (int i=0; i<n;i++) {
			counter++;
			if (colors[i]==0) {
				DFSVISIT2(i,1);
			}
		}
		for (int i=0; i<n; i++){
			if (art[i]==1) {
				out.print(i+1+" ");
			}
		}
		out.println("");
		for (int i=0; i<m; i++){
			out.print(anscol[i]+" ");
		}
    }
}