Coloring Edges

Description:

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

Sample Input:

4 5
1 2
1 3
3 4
2 4
1 4

Sample Output:

1
1 1 1 1 1 

Sample Input:

3 3
1 2
2 3
3 1

Sample Output:

2
1 1 2