D. Coloring Edgestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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.OutputIn 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).ExamplesInput
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 

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

1 1 1 1 1 1  
['constructive algorithms', 'dfs and similar', 'graphs', '*2100']