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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;


public class Main {


    static ArrayList<Integer>[] adjList;
    static int V, counter, SCC, dfs_num[], dfs_low[], SCCnum[], k, time[];
    static Stack<Integer> stack;
    static Edge[] edges;


    public static void main(String[] args) throws NumberFormatException, IOException {
        Scanner sc = new Scanner();
        PrintWriter out = new PrintWriter(System.out);
        V = sc.nextInt();
        adjList = new ArrayList[V];
        for (int i = 0; i < V; i++)
            adjList[i] = new ArrayList<>();
        int m = sc.nextInt();
        edges = new Edge[m];
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
            adjList[u].add(i);
            edges[i] = new Edge(u, v, i);
        }
        dfs_num = new int[V];
        dfs_low = new int[V];
        stack = new Stack<>();
        SCCnum = new int[V];
        Arrays.fill(SCCnum, -1);
        time = new int[V];
        Arrays.fill(time, -1);
        tarjanSCC();
        k = 1;
        counter = 0;
        for (int i = 0; i < V; i++)
            if (time[i] == -1) dfs(i);
        StringBuilder ans = new StringBuilder();
        for (Edge edge : edges) {
            int a = SCCnum[edge.u], b = SCCnum[edge.v];
            if (a != b || time[edge.u] < time[edge.v]) ans.append(1 + " ");
            else {
                k = 2;
                ans.append(2 + " ");
            }
        }
        out.println(k);
        out.println(ans);
        out.flush();
        out.close();
    }

    static void dfs(int u) {
        time[u] = counter++;
        for (int x : adjList[u]) {
            int v = edges[x].v;
            if (SCCnum[v] != SCCnum[u]) continue;
            if (time[v] == -1) dfs(v);
        }
    }

    static void tarjanSCC() {
        for (int i = 0; i < V; ++i)
            if (dfs_num[i] == 0)
                tarjanSCC(i);
    }

    static void tarjanSCC(int u) {
        dfs_num[u] = dfs_low[u] = ++counter;
        stack.push(u);

        for (int x : adjList[u]) {
            int v = edges[x].v;
            if (dfs_num[v] == 0)
                tarjanSCC(v);
            if (SCCnum[v] == -1)
                dfs_low[u] = Math.min(dfs_low[u], dfs_low[v]);
        }
        if (dfs_num[u] == dfs_low[u]) {
            while (true) {
                int v = stack.pop();
                SCCnum[v] = SCC;
                if (v == u)
                    break;
            }
            SCC++;
        }
    }

    static class Edge {
        int u, v, id, ans;

        public Edge(int u, int v, int id) {
            this.u = u;
            this.v = v;
            this.id = id;
            ans = 1;
        }
    }

    static class Scanner {
        BufferedReader br;
        StringTokenizer st;

        Scanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        int[] nextIntArray(int n) throws IOException {
            int[] ans = new int[n];
            for (int i = 0; i < n; i++)
                ans[i] = nextInt();
            return ans;

        }

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

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

}