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.*;

/**
 * @ClassName ColoringEdges
 * @auther mjlf
 * @Date 2019/9/9 15:17
 * @Description TODO
 */
public class ColoringEdges {

    public static Scanner scanner = new Scanner(System.in);
    public static int max = 1;

    public static void main(String[] args) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Node[] nodes = new Node[n+1];
        int[][] mm = new int[m][2];
        for (int i = 0; i < m; i++) {
            int num = scanner.nextInt();
            int next = scanner.nextInt();
            if (nodes[num] == null) {
                nodes[num] = new Node();
                nodes[num].setNum(num);
            }
            nodes[num].getNexts().add(next);
            mm[i][0] = num;
            mm[i][1] = next;
        }
        int[][] nn = new int[n+1][n+1];

        int currentColor = 1;
        for (int i = 1; i <= n; i++) {
            Map<Integer, Boolean> route = new HashMap<>();
            dfs(nodes, nn, i, route, currentColor);
        }

        System.out.println(max);
        for(int i = 0; i < m - 1; i ++){
            System.out.print(nn[mm[i][0]][mm[i][1]] + " ");
        }
        System.out.println(nn[mm[m-1][0]][mm[m-1][1]]);
    }

    public static void dfs(Node[] nodes, int[][] nn, int i, Map<Integer, Boolean> route, int currentColor) {
        if (nodes[i] != null) {
            if (nodes[i].getNexts() == null || nodes[i].getNexts().size() == 0) {
                return;
            }

            if (nodes[i].isSucceed()) {
                return;
            }

            //放到路上
            route.put(i, true);

            List<Integer> nexts = nodes[i].getNexts();
            for (int next : nexts) {
                //表示在路上
                if(route.containsKey(next)){
                    nn[i][next] = currentColor + 1;
                    if(max < currentColor + 1){
                        max = currentColor + 1;
                    }
                }else {
                    nn[i][next] = currentColor;
                    dfs(nodes, nn, next, route, currentColor);
                }
            }
            nodes[i].setSucceed(true);
            route.remove(i);
        }
    }

    static class Node {
        private int num;
        private List<Integer> nexts = new ArrayList<>();
        private boolean succeed;

        public int getNum() {
            return num;
        }

        public void setNum(int num) {
            this.num = num;
        }

        public List<Integer> getNexts() {
            return nexts;
        }

        public void setNexts(List<Integer> nexts) {
            this.nexts = nexts;
        }

        public boolean isSucceed() {
            return succeed;
        }

        public void setSucceed(boolean succeed) {
            this.succeed = succeed;
        }
    }
}