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

/**
 * Created by himanshubhardwaj on 11/10/19.
 * ALGO: Cycle in Directed Graph
 */
public class ColoringEdges {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str[] = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);

        Graph graph = new Graph(n);

        for (int i = 0; i < m; i++) {
            str = br.readLine().split(" ");
            graph.insert(i, Integer.parseInt(str[0]), Integer.parseInt(str[1]));
        }
        graph.DFS();
        StringBuilder sb = new StringBuilder();
        for (Edge e : graph.edges) {
            sb.append(e.colour);
            sb.append(" ");
        }
        System.out.println((graph.flag) ? 2 : 1);
        System.out.print(sb.toString());
    }

}


class Graph {
    ArrayList<Edge> adjList[];
    int startTime[];
    int endTime[];
    int numNodes;
    int clock = 0;
    ArrayList<Edge> edges;
    boolean flag = false;

    public Graph(int n) {
        this.numNodes = n;
        startTime = new int[n];
        endTime = new int[n];
        adjList = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new ArrayList();
        }
        edges = new ArrayList<>();
    }

    void insert(int index, int s, int d) {
        s--;
        d--;
        Edge e = new Edge(index, s, d);
        adjList[s].add(e);
        edges.add(e);
    }

    void DFS() {
        for (int i = 0; i < numNodes; i++) {
            if (startTime[i] == 0) {
                DFSHelper(i);
            }
        }
    }

    private void DFSHelper(int node) {
        clock++;
        startTime[node] = clock;

        for (Edge e : adjList[node]) {
            int neighbour = e.end;
            if (endTime[neighbour] == 0) {
                if (startTime[neighbour] != 0) {
                    if (startTime[neighbour] < startTime[node]) {
                        e.incrementColour();
                        flag = true;
                    }
                } else {
                    DFSHelper(neighbour);
                }
            }

        }


        clock++;
        endTime[node] = clock;
    }


}


class Node {
    int source;
    int destination;
}

class Edge {
    int index;
    int start;
    int end;
    int colour;

    public Edge(int index, int s, int e) {
        this.index = index;
        this.start = s;
        this.end = e;
        this.colour = 1;
    }

    void incrementColour() {
        colour++;
    }
}