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

输入输出样例

输入样例 #1

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

输出样例 #1

1
1 1 1 1 1 

输入样例 #2

3 3
1 2
2 3
3 1

输出样例 #2

2
1 1 2