CF1217D Coloring Edges

给定一个有 $n$ 个顶点和 $m$ 条有向边的有向图，图中没有自环和重边。 我们定义有向图的 $k$ 染色如下：你需要将每条边染成 $k$ 种颜色中的一种。如果不存在由同一种颜色的边组成的环，则称该 $k$ 染色是好的。 请你找到该有向图的一个好的 $k$ 染色，并且使 $k$ 尽可能小。

第一行包含两个整数 $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)$ 在边列表中最多只出现一次。

第一行输出一个整数 $k$，表示该有向图的一个好的 $k$ 染色所用的颜色数。 第二行输出 $m$ 个整数 $c_1, c_2, \dots, c_m$（$1 \le c_i \le k$），其中 $c_i$ 表示第 $i$ 条边（按输入顺序）的颜色编号。 如果有多组答案，输出任意一组（但 $k$ 必须最小）。

由 ChatGPT 4.1 翻译