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.util.ArrayList;
import java.util.List;

public class _Rough{
    static int n,m,count = 1;
    static List<Integer> list[];
    static boolean[] visited;
    static boolean[] rec;
    static int[] col;
    static int[] res;
    static ArrayList<Pair<Integer, Integer>> g[];
    static boolean cyc = false;
    static int ans = 1;
    static ArrayList<String> ch;
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));


    public static class Pair<L, R>{
        private L left;
        private R right;

        public void make_pair(L left, R right){
            this.left = left;
            this.right = right;
        }
        public L getLeft(){
            return left;
        }
        public R getRight(){
            return right;
        }

        public void setLeft(L left1){
            left = left1;
        }
        public void setRight(R right1){
            right = right1;
        }

    }


    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String[] s = in.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        list = new List[n];
        visited = new boolean[n];
        rec = new boolean[n];
        col = new int[n];
        ch = new ArrayList<>();
        g = new ArrayList[n];
        res = new int[m+1];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
            g[i] = new ArrayList<>();
//            g[i] = new Pair<Integer, Integer>();
        }

        for (Integer i = 0; i < m; i++) {
            s = in.readLine().split(" ");
            Integer a = Integer.parseInt(s[0]) - 1;
            Integer b = Integer.parseInt(s[1]) - 1;
            list[a].add(b);
            Pair p = new Pair<>();
            p.make_pair(b,i);
            g[a].add(p);
        }

//        System.out.println(Arrays.toString(list));

        for (int i = 0; i < n; i++) {
            if (col[i] == 0) {
                dfs(i);
            }
        }

        int ans = cyc ? 2 : 1;

        out.write(ans + "\n");
        for (int i = 0; i < m; i++) {
            out.write(res[i] + " ");
        }

        out.flush();
    }

    static void dfs(int v){

        col[v] = 1;
//        System.out.println(Arrays.toString(list));
        for (Pair<Integer, Integer> p :g[v]) {
            int to = p.getLeft(), id = p.getRight();
            if (col[to] == 0){
                dfs(to);
                res[id] = 1;
            }
            else if (col[to] == 2)
                res[id] = 1;
            else {
                res[id] = 2;
                cyc = true;
            }
        }
        col[v] = 2;
    }


}