H-有向图涂色

题目描述

给定一个有 $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$ 必须最小）。

输入输出样例 #1

输入 #1

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

输出 #1

1
1 1 1 1 1 

输入输出样例 #2

输入 #2

3 3
1 2
2 3
3 1

输出 #2

2
1 1 2