← 返回题目列表

Codeforces · 1217/D

D. 边缘着色

中文机器翻译题面 查看原题

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