Problem: You are given a directed graph with n vertices and m directed edges without self-loops or multiple edges.

Let's denote the k-coloring of a digraph as following: you color each edge in one of k colors. The k-coloring is good if and only if there no cycle formed by edges of same color.

Find a good k-coloring of given digraph with minimum possible k.

Input

The first line contains two integers n and m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 5000) — the number of vertices and edges in the digraph, respectively.

Next m lines contain description of edges — one per line. Each edge is a pair of integers u and v (1 ≤ u, v ≤ n, u ≠ v) — there is directed edge from u to v in the graph.

It is guaranteed that each ordered pair (u, v) appears in the list of edges at most once.

Output

In the first line print single integer k — the number of used colors in a good k-coloring of given graph.

In the second line print m integers c_1, c_2, ..., c_m (1 ≤ c_i ≤ k), where c_i is a color of the i-th edge (in order as they are given in the input).

If there are multiple answers print any of them (you still have to minimize k).

Examples

Input


4 5
1 2
1 3
3 4
2 4
1 4


Output


1
1 1 1 1 1 


Input


3 3
1 2
2 3
3 1


Output


2
1 1 2 

Solution (in JAVA):

Solution:

import java.io.*;
import java.util.*;
public class D1217 
{
    static int n,m,vis[],a[],edge[],r,cyc;
    static HashMap<Integer,HashSet<Integer>> map;
    
    public static void main(String args[])throws IOException
    {
        Reader sc=new Reader();
        n=sc.nextInt();
        m=sc.nextInt();
        a=new int[n+1];
        map=new HashMap<>();
        r=1;
        edge=new int[m+1];
        for(int i=1;i<=m;i++)
        {
            int x=sc.nextInt();
            int y=sc.nextInt();
            if(a[x]==0)
                map.put(x,new HashSet<>());
            if(a[y]==0)
                map.put(y,new HashSet<>());
            
            a[x]=a[y]=1;
            map.get(x).add(y);
            if(check())
            {
                edge[i]=2;r=2;
                map.get(x).remove(y);
                map.get(y).add(x);
            }
            else
                edge[i]=1;
            
        }
        System.out.println(r);
        for(int i=1;i<=m;i++)
        {
            System.out.print(edge[i]+" ");
        }
    }
    static boolean check()
    {
        vis=new int[n+1];
        
        for(int i=1;i<=n;i++)
        {
            if(a[i]==1 && vis[i]==0)
            {
                
                cyc=0;
                dfs(i);
                if(cyc==1)
                    return true;
            }
                
        }
        return false;
    }
    static void dfs(int ind)
    {
        vis[ind]=1;
        for(int i:map.get(ind))
        {
            if(vis[i]==0)
            {
                dfs(i);
            }
            else if(vis[i]==1)
            {
                cyc=1;
            }
        }
        vis[ind]=2;
    }

}

class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte [] buffer;
		private int bufferPointer, bytesRead;
		
		public Reader () {
			din = new DataInputStream (System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
		
		public Reader (String file_name) throws IOException {
			din = new DataInputStream (new FileInputStream (file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
		
		public String readLine () throws IOException {
			byte [] buf = new byte[1024];
			int cnt = 0, c;
			while ((c = read ()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String (buf, 0, cnt);
		}
		
		public int nextInt () throws IOException {
			int ret = 0;
			byte c = read ();
			while (c <= ' ')
				c = read ();
			boolean neg = (c == '-');
			if (neg)
				c = read ();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read ()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
		
		public long nextLong () throws IOException {
			long ret = 0;
			byte c = read ();
			while (c <= ' ')
				c = read ();
			boolean neg = (c == '-');
			if (neg)
				c = read ();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read ()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
		
		public double nextDouble () throws IOException {
			double ret = 0, div = 1;
			byte c = read ();
			while (c <= ' ')
				c = read ();
			boolean neg = (c == '-');
			if (neg)
				c = read ();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read ()) >= '0' && c <= '9');
			if (c == '.')
				while ((c = read ()) >= '0' && c <= '9')
					ret += (c - '0') / (div *= 10);
			if (neg)
				return -ret;
			return ret;
		}
		
		private void fillBuffer () throws IOException {
			bytesRead = din.read (buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}
		
		private byte read () throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer ();
			return buffer[bufferPointer++];
		}
		
		public void close () throws IOException {
			if (din == null)
				return;
			din.close ();
		}
	}