CF1217D.Coloring Edges

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$ .

The first line contains two integers $n$ and $m$ ( $2 \le n \le 5000$ , $1 \le m \le 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 \le u, v \le n$ , $u \ne 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.

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, \dots, c_m$ ( $1 \le c_i \le 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$ ).