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

public class Main {

    static final int FRESH = 0;
    static final int ACTIVE = 1;
    static final int DONE = 2;

    static final int WHITE = 1;
    static final int BLACK = 2;
    static int colors = 1;

    static class Edge {
        int from;
        int to;
        int color;

        public Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }

    static void color(int u, List<List<Edge>> adj, int[] status) {
        status[u] = ACTIVE;
        for (Edge e : adj.get(u)) {
            if (status[e.to] == ACTIVE) {
                colors = 2;
                e.color = BLACK;
            } else {
                e.color = WHITE;
                if (status[e.to] == FRESH) color(e.to, adj, status);
            }
        }
        status[u] = DONE;
    }

    static void dfs(int s, List<List<Edge>> adj, int[] status, int[] next) {
        LinkedList<Integer> stack = new LinkedList<>();
        stack.add(s);
        status[s] = ACTIVE;

        while (!stack.isEmpty()) {
            int u = stack.peekLast();

            if (next[u] >= adj.get(u).size()) {
                stack.pollLast();
                status[u] = DONE;
                continue;
            }

            Edge e = adj.get(u).get(next[u]);
            next[u]++;

            if (status[e.to] == ACTIVE) {
                colors = 2;
                e.color = BLACK;
            } else {
                e.color = WHITE;
                if (status[e.to] == FRESH) {
                    status[e.to] = ACTIVE;
                    stack.addLast(e.to);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        List<List<Edge>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        Edge[] edges = new Edge[m];

        for (int i = 0; i < m; i++) {
            Edge e = new Edge(sc.nextInt() - 1, sc.nextInt() - 1);
            edges[i] = e;
            adj.get(e.from).add(e);
        }

        int[] status = new int[n];
        int[] next = new int[n];

        for (int i = 0; i < n; i++) {
            if (status[i] == FRESH) dfs(i, adj, status, next);
        }

        System.out.println(colors);

        for (Edge e : edges) System.out.print(e.color + " ");
    }
}