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