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.util.*;
import java.io.*;

public class Main {
	static final int MOD_PRIME = 1000000007;

	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();

		int i = 0;
		int t = 1;
		// t = in.nextInt();
		for (; i < t; i++)
			solver.solve(i, in, out);

		out.close();
	}

	static class Task {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int n = in.nextInt();
			int m = in.nextInt();
			HashMap<String , Integer> edge = new HashMap<String, Integer>();
			HashMap<Integer , ArrayList<Integer>> adj = new HashMap<Integer, ArrayList<Integer>>();
			Set<Integer> open = new HashSet<Integer>();
			Set<Integer> ans = new HashSet<Integer>();
			
			boolean[] vis = new boolean[n];
			for(int i = 0;i < m;i++) {
				int u = in.nextInt() - 1;
				int v = in.nextInt() - 1;
				edge.put(String.valueOf(u) + " " + String.valueOf(v), i);
				if(!adj.containsKey(u)) adj.put(u , new ArrayList<Integer>());
				adj.get(u).add(v);
			}
			
			for(int i = 0;i < n; i++) {
				if(!vis[i]) {
					dfs(adj , ans , open, edge , vis ,i);
				}
			}
			
			out.println(ans.size() == 0 ? 1 : 2);
			for(int i = 0; i < m ; i++) out.print((ans.contains(i) ? 2 : 1) + " ");
//			out.println();
//			for(int k : ans) {
//				out.println(k + " ");
//				
//			}
		}

	}

	// template code

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

	}

	static long modexp(long a, long b, long p) {
		// returns a to the power b mod p by modular exponentiation

		long res = 1;
		long mult = a % p;
		while (b > 0) {
			if (b % 2 == 1) {
				res = (res * mult) % p;
			}
			b /= 2;
			mult = (mult * mult) % p;
		}

		return res;
	}

	static double log(double arg, double base) {
		// returns log of a base b, contains floating point errors, dont use for exact
		// calculations.

		if (base < 0 || base == 1) {
			throw new ArithmeticException("base cant be 1 or negative");
		}
		if (arg < 0) {
			throw new ArithmeticException("log of negative number undefined");
		}
		return Math.log10(arg) / Math.log10(base);
	}

	static int gcd(int a, int b) {
		if (b == 0) {
			return a;
		}

		return gcd(b, a % b);

	}

	static long gcd(long a, long b) {
		if (b == 0) {
			return a;
		}

		return gcd(b, a % b);

	}

	//scope for improvement
	static ArrayList<Integer> sieveOfEratosthenes(int n) {
		boolean[] check = new boolean[n + 1];
		ArrayList<Integer> prime = new ArrayList<Integer>();
		for (long i = 2; i <= n; i++) {
			if (!check[(int)i]) {
				prime.add((int)i);
				for (long j = i * i; j <= n; j += i) {
					check[(int)j] = true;
				}
			}
		}

		return prime;
	}
	
	static int modInverse(int a, int n) {
		//returns inverse of a mod n by extended euclidean algorithm
		int t = 0;
		int newt = 1;
		int r = n;
		int newr = a;
		int quotient;
		int tempr, tempt;
		while (newr != 0) {
			quotient = r / newr;
			tempt = newt;
			tempr = newr;
			newr = r - quotient * tempr;
			newt = t - quotient * tempt;
			t = tempt;
			r = tempr;
		}
		if (r > 1) {
			throw new ArithmeticException("inverse of " + a + " mod " + n + " does not exist");
		} else {
			if(t < 0) {
				t += n;
			}
			return t;
		}
	}
	
	static int primeModInverse(int a , int n) {
		//returns inverse of a mod n by mod exponentiation, use only if n is prime
		return (int)modexp(a, n-2, n);
	}
	
	static void dfs(HashMap<Integer , ArrayList<Integer>> adj , Set<Integer> ans , Set<Integer> open ,HashMap<String , Integer> edge, boolean[] vis, int i) {
		vis[i] = true;
		open.add(i);
		if(adj.get(i) != null) {
			for(int k : adj.get(i)) {
				if(!vis[k]) {
					dfs(adj , ans , open, edge , vis ,k);
				}else if(open.contains(k)){
					ans.add(edge.get(String.valueOf(i) + " " + String.valueOf(k)));
				}
			}
		}
		
		open.remove(i);
		
	}
}