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:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class D
   {
      private final int V; 
	private final List<List<Integer>> adj; 

	public D(int V) 
	{ 
		this.V = V; 
		adj = new ArrayList<>(V); 
		
		for (int i = 0; i < V; i++) 
			adj.add(new LinkedList<>()); 
	} 
	
	// This function is a variation of DFSUtil() in 
	// https://www.geeksforgeeks.org/archives/18212 
	private boolean isCyclicUtil(int i, boolean[] visited, 
									boolean[] recStack) 
	{ 
		
		// Mark the current node as visited and 
		// part of recursion stack 
		if (recStack[i]) 
			return true; 

		if (visited[i]) 
			return false; 
			
		visited[i] = true; 

		recStack[i] = true; 
		List<Integer> children = adj.get(i); 
		
		for (Integer c: children) 
			if (isCyclicUtil(c, visited, recStack)) 
				return true; 
				
		recStack[i] = false; 

		return false; 
	} 

	private void addEdge(int source, int dest) { 
		adj.get(source).add(dest); 
	} 

	// Returns true if the graph contains a 
	// cycle, else false. 
	// This function is a variation of DFS() in 
	// https://www.geeksforgeeks.org/archives/18212 
	private boolean isCyclic() 
	{ 
		
		// Mark all the vertices as not visited and 
		// not part of recursion stack 
		boolean[] visited = new boolean[V]; 
		boolean[] recStack = new boolean[V]; 
		
		
		// Call the recursive helper function to 
		// detect cycle in different DFS trees 
		for (int i = 0; i < V; i++) 
			if (isCyclicUtil(i, visited, recStack)) 
				return true; 

		return false; 
	}
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int M = Integer.parseInt(st.nextToken());
         LinkedList<Edge>[] edges = new LinkedList[N+1];
         for(int i=1; i <= N; i++)
            edges[i] = new LinkedList<Edge>();
         int[] res = new int[M];
         int[] color = new int[N+1];
         int[] color2 = new int[M];
         for(int i=0; i < M; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(new Edge(i,b));
            color2[i] = 1;
            if(a > b)
                color2[i]++;
         }
         for(int i=1; i <= N; i++)
            if(color[i] == 0)
            {
               color[i] = 1;
               boolean[] seen = new boolean[N+1];
               dfs(i, edges, seen, res, color);
            }
         //why am I stupid
         D graph = new D(5001); 
   		for(int i=1; i <= N; i++)
            for(Edge e: edges[i])
               graph.addEdge(i, e.to);
         cycle = graph.isCyclic(); 
         StringBuilder sb = new StringBuilder();
         if(cycle)
         {
            res = color2;
            sb.append("2\n");
            for(int x: res)
               sb.append(x+" ");
            System.out.println(sb);
         }
         else
         {
            sb.append("1\n");
            for(int x: res)
               sb.append(1+" ");
            System.out.println(sb);
         }
      }
      static boolean cycle = false;
      public static void dfs(int curr, LinkedList<Edge>[] edges, boolean[] seen, int[] res, int[] color)
      {
         seen[curr] = true;
         for(Edge e: edges[curr])
         {
            int next = e.to;
            res[e.id] = color[curr];
            if(!seen[next] && color[next] == 0)
            {
               color[next] = (color[curr] == 1) ? 2: 1;
               dfs(next, edges, seen, res, color);
            }
            else if(seen[next])
               cycle = true;
         }
      }
   }
   class Edge
   {
      public int to;
      public int id;
      
      public Edge(int a, int b)
      {
         to = b;
         id = a;
      }
   }