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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class CFER72 {
 
static ArrayList<Pair>[] adjList;
static int[] ans;
static int[]visited;
static int UNVISITED=0,explore=-1,vis=1;
public static void main(String[] args)throws Exception {
	 PrintWriter pw=new PrintWriter(System.out);
	 Scanner sc=new Scanner(System.in);
	 int n=sc.nextInt();
	 int m=sc.nextInt();
	adjList=new ArrayList[n];
	for(int i=0;i<n;i++)
		adjList[i]=new ArrayList();
	for(int i=0;i<m;i++) 
		adjList[sc.nextInt()-1].add(new Pair(sc.nextInt()-1,i));
	int k=1;
visited= new int[n];
	ans=new int[m];
	for(int i=0;i<n;i++)
		if(visited[i]==0)
			bfs(i);
	int max=1;
	StringBuilder sb=new StringBuilder();
	for(int i=0;i<m;i++)
		{
		sb.append(ans[i]+" ");
		if(ans[i]==2)max=2;
		}
	pw.println(max);
	pw.println(sb.toString());
	
	pw.flush();
}

public static  void bfs(int u) {
	visited[u]=explore;
	for(Pair p :adjList[u]) {
		int v=p.a;
		int idx=p.b;
		if(visited[v]==vis) {
			ans[idx]=1;
			continue;
		}else if(visited[v]==explore) {
			ans[idx]=2;
		}else {
			ans[idx]=1;
			bfs(v);
		}
	}
	visited[u]=vis;
}
public static void shuffle(int[] a)
{
	int n = a.length;
	for(int i = 0; i < n; i++)
	{
		int r = i + (int)(Math.random() * (n - i));
		int tmp = a[i];
		a[i] = a[r];
		a[r] = tmp;
	}
}
static int INF=(int)1e9;

static class Pair{
	int a,b;
	
public Pair(int x,int y) {
		a=x;b=y;
	}
	
}
static class Scanner 
{
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

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

	public int nextInt() throws IOException {return Integer.parseInt(next());}
	
	public long nextLong() throws IOException {return Long.parseLong(next());}

	public String nextLine() throws IOException {return br.readLine();}
	
	public double nextDouble() throws IOException
	{
		String x = next();
		StringBuilder sb = new StringBuilder("0");
		double res = 0, f = 1;
		boolean dec = false, neg = false;
		int start = 0;
		if(x.charAt(0) == '-')
		{
			neg = true;
			start++;
		}
		for(int i = start; i < x.length(); i++)
		{	if(x.charAt(i) == '.')
			{
				res = Long.parseLong(sb.toString());
				sb = new StringBuilder("0");
				dec = true;
			}
			else
			{
				sb.append(x.charAt(i));
				if(dec)
					f *= 10;
			}
		if(sb.length()==18) {
			res+=Long.parseLong(sb.toString()) / f;
			sb=new StringBuilder("0");
		}
		}
		res += Long.parseLong(sb.toString()) / f;
		return res * (neg?-1:1);
	}
	
	public boolean ready() throws IOException {return br.ready();}


}
}