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.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;
/*
5 5
.....
.###.
....#
.....
.....


 * 
 * 
 */
public class D {
	
	static class Edge {
		int from, to;
		public Edge(int from, int to) {
			this.from=from;
			this.to=to;
		}
	}
	
	static class Node {
		int inDegree=0;
		ArrayList<Node> to=new ArrayList<>();
		
		void dfs() {
			for (Node n:to) {
				n.inDegree--;
				if (n.inDegree==0)
					n.dfs();
			}
		}
	}

	public static void main(String[] args) {
		FastScanner fs=new FastScanner();
		int n=fs.nextInt(), m=fs.nextInt();
		Node[] nodes=new Node[n];
		Edge[] edges=new Edge[m];
		for (int i=0; i<n; i++) nodes[i]=new Node();
		for (int i=0; i<m; i++) {
			int a=fs.nextInt()-1, b=fs.nextInt()-1;
			edges[i]=new Edge(a, b);
			nodes[b].inDegree++;
			nodes[a].to.add(nodes[b]);
		}
		ArrayDeque<Node> toRemove=new ArrayDeque<>();
		for (int i=0; i<n; i++)
			if (nodes[i].inDegree==0)
				toRemove.add(nodes[i]);
		for (Node nn:toRemove)
			nn.dfs();
		boolean cycle=false;
		for (Node nn:nodes)
			if (nn.inDegree!=0) cycle=true;
		if (cycle) {
			System.out.println(2);
			for (Edge e:edges)
				if (e.from<e.to)
					System.out.print(1+" ");
				else 
					System.out.print(2+" ");
		}
		else {
			System.out.println(1);
			for (int i=0; i<m; i++)
				System.out.print(1+" ");
			System.out.println();
		}
	}

	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		public String next() {
			while(!st.hasMoreElements())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
				}
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}