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

public class Main
{
	PrintWriter out = new PrintWriter(System.out);
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok = new StringTokenizer("");
    String next() throws IOException {
        if (!tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine()); }
        return tok.nextToken();
    }
    int ni() throws IOException { return Integer.parseInt(next()); }
    long nl() throws IOException { return Long.parseLong(next()); }
  
    static ArrayList<Integer>[]A;
    static ArrayList<Integer>[]B;
    static ArrayList<Integer>[]C;
    static int n,m;
  
    void solve() throws IOException {
        n=ni();
        m=ni();
        A=new ArrayList[n+1];
        B=new ArrayList[n+1];
        C=new ArrayList[n+1];
        for (int x=1;x<=n;x++) {
            A[x]=new ArrayList();
            B[x]=new ArrayList();
            C[x]=new ArrayList();
        }
        
        for (int x=1;x<=m;x++) {
            int p=ni(),q=ni();
            A[p].add(q);
            B[p].add(x);
            C[p].add(1);
        }
        
        int c=1;
        while (!dfs(c)) c++;
        
        int[] E=new int[m+1];
        for (int x=1;x<=n;x++) {
            for (int y=0;y<A[x].size();y++) {
                E[B[x].get(y)]=C[x].get(y);
            }
        }
        
        System.out.println(c);
        for (int x=1;x<=m;x++) out.print(E[x]+" ");
        out.println();
        out.flush();
        
    }
    
    boolean dfs (int c) {
        int[]D=new int[n+1];
        boolean f=true;
        for (int x=1;x<=n;x++) {
            if (D[x]==0) {
                if (!dfs2(x,c,D)) f=false;
            }
        }
        return f;
    }
    
    boolean dfs2(int p, int c, int[] D) {
        boolean f=true;
        D[p]=1;
        for (int x=0;x<A[p].size();x++) {
            if (C[p].get(x)<c) continue;
            int q=A[p].get(x);
            if (D[q]==2) continue;
            if (D[q]==1) {
                f=false;
                C[p].set(x,c+1);
                continue;
            }
            if (!dfs2(q,c,D)) f=false;
        }
        D[p]=2;
        return f;
    }
    
    public static void main(String[] args) throws IOException {
        new Main().solve();
    }
}