Coloring Edges
Description
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$).
Input
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.
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, \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$).
Samples
4 5
1 2
1 3
3 4
2 4
1 4
1
1 1 1 1 1
3 3
1 2
2 3
3 1
2
1 1 2