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 sun.util.resources.cldr.ar.CalendarData_ar_YE;

import java.io.*;
import java.util.*;
public class l {
    ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////                                                                                                               /////////
////////                                                                                                               /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM         OOOOOO             SSSSSSS      EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMMMM      MMMMMM      OOO      OOO        SSSS   SSS     EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEE           MMMM MMM  MMM MMMM    OOO          OOO    SSSS       SSS   EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM  MMMMMM  MMMM   OOO            OOO   SSSS             EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM  OOO              OOO   SSSSSSS         EEEEE          /////////
////////   HHHHHHHHHHHHHHHH  EEEEEEEEEEE     MMMM          MMMM  OOO              OOO      SSSSSS       EEEEEEEEEEE    /////////
////////   HHHHHHHHHHHHHHHH  EEEEEEEEEEE     MMMM          MMMM  OOO              OOO         SSSSSSS   EEEEEEEEEEE    /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM   OOO            OOO              SSSS  EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM    OOO          OOO     SSS       SSSS  EEEEE          /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM      OOO      OOO        SSS    SSSS    EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM         OOOOOO             SSSSSSS      EEEEEEEEEEEEE  /////////
////////                                                                                                               /////////
////////                                                                                                               /////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    static int[][]adjmat;
    static int[]ans;
    static int max;
    static ArrayList<Integer>[]adj;
    static void dfs(int node,int ret,int c){
        inpath.add(node);
        for (int i :adj[node]) {
            if (i<ret||inpath.contains(i)){
                continue;
            }
            else {
                if (i==ret){
                    ans[adjmat[node][i]]=c+1;
                }
                else {
                    dfs(i,ret,c);
                }
            }
        }
    }
    static HashSet<Integer>inpath;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        int m = sc.nextInt();
        adjmat= new int[n][n];
        adj= new ArrayList[n];
        for (int i =0;i<n;i++)adj[i]=new ArrayList<>();
        for (int i =1;i<=m;i++){
            int u = sc.nextInt()-1;
            int v = sc.nextInt()-1;
            adj[u].add(v);
            adjmat[u][v]=i;
        }
        inpath= new HashSet<>();
        ans= new int[m+1];
        for (int i =0;i<n;i++){
            for (int j =i+1;j<n;j++){
                if (adjmat[i][j]>0){
                    inpath.clear();
                    dfs(j,i,ans[adjmat[i][j]]);
                }
            }
        }
        for (int i =1;i<=m;i++)max=Math.max(max,ans[i]);
        pw.println(max+1);
        for (int i =1;i<=m;i++){
            pw.print((ans[i]+1)+" ");
        }
        pw.flush();
    }
    static public class Edge implements Comparable<Edge> {
        int node, cost;

        Edge(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

        @Override
        public String toString() {
            return node + " " + cost;
        }

        @Override
        public int compareTo(Edge o) {
            return cost - o.cost;
        }
    }

//
//    static class pair implements Comparable<pair>{
//        int u,v;
//        pair(int a,int b){
//            u=a;
//            v=b;
//        }
//
//        @Override
//        public int compareTo(pair pair) {
//            return u==pair.u?v-pair.v:u-pair.u;
//        }
//    }
//    static class Edge implements Comparable<Edge>{
//        int node,cost;
//        Edge(int a,int b){
//            node=a;
//            cost=b;
//        }
//
//        @Override
//        public int compareTo(Edge edge) {
//            return edge.cost-cost;
//        }
//    }
//    static long gcd(long a, long b) {
//        if (a == 0) return b;
//        return gcd(b % a, a);
//    }
//
//    static int inver(long x, int mod) {
//        int a = (int) x;
//        int e = (mod - 2);
//        int res = 1;
//        while (e > 0) {
//            if ((e & 1) == 1) {
//                //System.out.println(res*a);
//                res = (int) ((1l * res * a) % mod);
//            }
//            a = (int) ((1l * a * a) % mod);
//            e >>= 1;
//        }
//        //out.println(res+" "+x);
//        return res % mod;
//    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

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

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

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

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }


}