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

public class Es4
{
    static IO io = new IO();
	static ArrayList<IntegerPair>[] adjList;
    public static void main(String[] args)
    {
		int n = io.getInt();
		int m = io.getInt();
		adjList = new ArrayList[n];
		for(int i=0; i<n; i++)
			adjList[i] = new ArrayList<>();
		
		for(int i=0; i<m; i++){
			int u=io.getInt()-1;
			int v=io.getInt()-1;
			adjList[u].add(new IntegerPair(v, false, i));
		}
		visited = new int[n];
		for(int i=0; i<n; i++){
			if(visited[i]==0)
				cycleDfs(i);
		}
		ArrayList<IntegerPair> list = new ArrayList<IntegerPair>();
		for(ArrayList<IntegerPair> a : adjList)
			for(IntegerPair ip : a)
				list.add(ip);
		Collections.sort(list);
		if(hasCycle)
			io.println(2);
		else
			io.println(1);
		for(int i=0; i<m; i++){
			io.print((list.get(i).b ? 2 : 1) + " ");
		}
		
        io.close();
    }
	
	static int[] visited;
	static boolean hasCycle = false;
	static void cycleDfs(int v){ 
		visited[v] = 1;
		for(int i=0; i< (int)adjList[v].size(); i++){
			if(visited[(int)adjList[v].get(i).a]==0){
				cycleDfs((int)adjList[v].get(i).a);
			}
			else if(visited[(int)adjList[v].get(i).a]==1){
				adjList[v].get(i).b = true;
				hasCycle = true;
			}
		}
		visited[v] = 2;
    }
}

class IntegerPair implements Comparable<IntegerPair>{
	int a;
	boolean b;
	int c;
	public IntegerPair(int _a, boolean _b, int _c)
	{
		a = _a;
		b = _b;
		c = _c;
	}
	
	@Override
	public int compareTo(IntegerPair o){
		return c-o.c;
	}
}

class IO extends PrintWriter {
	public IO() {
        super(new BufferedOutputStream(System.out));
        r = new BufferedReader(new InputStreamReader(System.in));
    }

    public IO(String fileName) {
        super(new BufferedOutputStream(System.out));
        try{
            r = new BufferedReader(new FileReader(fileName));
        } catch (FileNotFoundException e) {
            this.println("File Not Found");
        }
    }

    public boolean hasMoreTokens() {
        return peekToken() != null;
    }

    public int getInt() {
        return Integer.parseInt(nextToken());
    }

    public double getDouble() {
        return Double.parseDouble(nextToken());
    }

    public long getLong() {
        return Long.parseLong(nextToken());
    }

    public String getWord() {
        return nextToken();
    }

	public String getLine(){
        try{
            st = null;
            return r.readLine();
        }
        catch(IOException ex){}
        return null;
    }
	

    private BufferedReader r;
    private String line;
    private StringTokenizer st;
    private String token;

    private String peekToken() {
        if (token == null)
            try {
                while (st == null || !st.hasMoreTokens()) {
                    line = r.readLine();
                    if (line == null) return null;
                    st = new StringTokenizer(line);
                }
                token = st.nextToken();
            } catch (IOException e) { }
        return token;
    }

    private String nextToken() {
        String ans = peekToken();
        token = null;
        return ans;
    }
}