给你一个有向图,其中有 $$$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
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