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