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 static java.lang.Math.*;
import static java.util.Arrays.* ;

import java.util.*;
import java.io.*;

public class B
{
    int [][] ans ;
    int [][] num ;
    int [] status , head , to , next ;
    int time ;
    void addEdge(int a , int b)
    {
        next[++time] = head[a] ;
        head[a] = time ;
        to[time] = b ;
    }

    void dfs(int u)
    {
        status[u] = 1 ;
        for(int i = head[u] ; i != 0 ; i = next[i]) {
            int v = to[i];

            if (status[v] == 0) {
                ans[u][v] = 1;
                dfs(v);
            } else if (status[v] == 1)
                ans[u][v] = 2;
            else
                ans[u][v] = 1;
        }
        status[u] = 2 ;
    }

    void main() throws Exception
    {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt() , m = sc.nextInt() ;
        head = new int [n] ;
        to = new int [m + 1] ;
        next = new int [m + 1] ;
        num = new int [n][n] ;
        ans = new int [n][n] ;
        for(int i = 0 ; i < n; i ++)fill(num[i] , -1);
        for(int i = 0 ; i < m ; i ++)
        {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1 ;
            num[u][v] = i ;
            addEdge(u , v);
        }
        status = new int [n] ;
        for(int i = 0 ; i < n ; i++)
            if(status[i] == 0)
                dfs(i) ;
        int [] print = new int [m] ;
        int k= 0 ;
        for(int i = 0 ; i < n ; i ++)
            for(int j = 0 ; j < n ; j++)
            if(num[i][j] >= 0)
                k = max(k , print[num[i][j]] = ans[i][j]) ;
        out.println(k);
        for(int x : print)
            out.println(x);
        out.flush();
        out.close();
    }

    class Scanner
    {
        BufferedReader br;
        StringTokenizer st;

        Scanner(InputStream in)
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

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

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

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

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

    public static void main (String [] args) throws Exception {(new B()).main();}

}