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.*;
import java.math.*;
import java.security.*;
import java.text.DecimalFormat;
import java.util.*;

public class Main {
    private static LinkedList<Integer> [] edges;
    private static int [] fr, to, color, edge_color;


    private static void dfs(int u, int ie) {
        if (color[u] == 2) return;
        color[u] = 1;
        for (int e : edges[u]) if (e != ie){
            int v = fr[e] + to[e] - u;
            if (color[v] == 1) edge_color[e] = 1;
            else {
                dfs(v, e);
            }
        }
        color[u] = 2;
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        IO io = new IO(null, null);
        int n = io.getNextInt(), m = io.getNextInt();
        edges = new LinkedList[n];
        for (int i = 0; i < n; i++) edges[i] = new LinkedList<>();
        fr = new int[m];
        to = new int[m];
        color = new int[n];
        edge_color = new int[m];

        for (int e = 0; e < m; e++){
            fr[e] = io.getNextInt() - 1;
            to[e] = io.getNextInt() - 1;
            edges[fr[e]].add(e);
        }

        for (int i = 0; i < n; i++)
            if (color[i] == 0)
                dfs(i, -1);

        int k = 0;
        for (int e = 0; e < m; e++) k = Math.max(k, edge_color[e]);
        io.println(k+1);
        for (int e = 0; e < m; e++)
            io.print((edge_color[e]+1) + " ");
        io.println("");
        io.close();
    }
}

class pollardRho{
    private static BigInteger zero = new BigInteger("0");
    private static BigInteger one  = new BigInteger("1");
    private static BigInteger two  = new BigInteger("2");
    private static SecureRandom r = new SecureRandom();
    private static Queue<BigInteger> tasks = new LinkedList<>();
    private static ArrayList<BigInteger> primes = new ArrayList<>();

    public static long getBiggestPrime(long n) {
        long N = n;
        tasks.clear();
        primes.clear();
        tasks.add(BigInteger.valueOf(n));
        while (!tasks.isEmpty()){
            BigInteger x = tasks.poll();
            BigInteger P = one;
            for (BigInteger p : primes)
                if (P.compareTo(p) < 0)
                    P = p;
            for (BigInteger p : primes){
                while (x.remainder(p).equals(zero))
                    x = x.divide(p);
            }
//            System.err.println(x + " " + P);
            if(x.compareTo(P) <= 0) continue;
            factor(x);
        }
        BigInteger P = one;
        for (BigInteger p : primes)
            if (P.compareTo(p) < 0)
                P = p;
//        System.out.println(N + " " + tasks + " " + primes);
        return P.longValue();
    }

    private static void factor(BigInteger N) {
        if (N.compareTo(one) == 0) return;
        if (N.isProbablePrime(20)) {
            primes.add(N);
            return;
        }
        BigInteger d = rho(N);

        if (d.compareTo(one) != 0)
            tasks.add(d);
        N = N.divide(d);
        if (N.compareTo(one) != 0)
            tasks.add(N);
    }

    private static BigInteger rho(BigInteger N) {
        BigInteger d;
        BigInteger c  = new BigInteger(N.bitLength(), r);
        BigInteger p  = new BigInteger(N.bitLength(), r);
        BigInteger q = p;

        if (N.mod(two).compareTo(zero) == 0) return two;

        d = one;
        while(d.compareTo(one) == 0) {
            p  =  p.multiply(p).mod(N).add(c).mod(N);
            q = q.multiply(q).mod(N).add(c).mod(N);
            q = q.multiply(q).mod(N).add(c).mod(N);
            d = p.subtract(q).gcd(N);
        }
        return d;
    }
}
class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}