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

给你一个包含 $n$ 个顶点和 $m$ 条有向边的有向图，图中不含自环或重边。

我们定义有向图的 $k$-染色如下：将每条边染成 $k$ 种颜色之一。当且仅当不存在由同一种颜色的边构成的有向环时，该 $k$-染色称为“好”的。

请为给定的有向图找出一个“好”的 $k$-染色，使得 $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.

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 5000$，$1 \le m \le 5000$），分别表示有向图中的顶点数和边数。

接下来的 $m$ 行描述各条边，每行一条边。每条边由一对整数 $u$ 和 $v$（$1 \le u, v \le n$，且 $u \ne v$）组成，表示图中存在一条从 $u$ 指向 $v$ 的有向边。

保证在边列表中，每个有序对 $(u, v)$ 至多出现一次。

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

第一行输出一个整数 $k$ —— 给定图的一个良好 $k$-着色中所使用的颜色数。

第二行输出 $m$ 个整数 $c_1, c_2, \dots, c_m$（其中 $1 \le c_i \le k$），$c_i$ 表示第 $i$ 条边的颜色（按输入中给出的顺序）。

若存在多个答案，输出任意一个即可（但你仍需使 $k$ 最小）。