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.

分析

对我这个菜鸡来说，去染色返祖边的操作并不怎么显然……算了……

没能坚持只有2种颜色的猜想。挂城墙。

没必要挂代码。