← 返回题目列表

AtCoder · ttpc2022_h

H. 彩色图

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

配点 : 300 点

注意

本题的内存限制为 256 MB。

問題文

N 頂点 M 给定一个有向边的图。顶点有 1 减去 N 号码位于侧面。 它的编号为 1 减去 M 。侧面 i (1 ≤ i ≤ M) 是顶点 A_i 到顶点 B_i 指向的边。

你需要用颜色 1, …, N 之一为图的每个顶点上色。但是,顶点 i (1 ≤ i ≤ N上的颜色设为 c_i 时,需要满足以下条件。

  • 对任意组合 (i, j) (1 ≤ i < j ≤ N), 计算c_i = c_j 顶点 i 到顶点 j 存在到顶点的路径,或者到顶点的路径(可以两者都有)。 j 到顶点 i 至少存在一条路径(可以两者都存在)。

\max\{c_1, …, c_N\} 输出使 1 请构建一个。

制約

  • 所有输入均为整数
  • 1 ≤ N ≤ 7 \times 10^3
  • 0 ≤ M ≤ 7 \times 10^3
  • 1 ≤ A_i, B_i ≤ N (1 ≤ i ≤ M)
  • A_i ≠ B_i (1 ≤ i ≤ M)
  • (A_i, B_i) ≠ (A_j, B_j) (1 ≤ i < j ≤ M)

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

\max\{c_1, …, c_N\} 最小的上色方式,格式如下。

c_1 c_2 \cdots c_N

入力例 1

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

出力例 1

1 1 1 2 1

頂点 2 → 5 → 1 → 4 由于存在路径,所以可以将顶点 1, 2, 4, 5 涂成相同颜色。

頂点 3, 4 之间不存在路径,因此2 需要至少这么多颜色。


入力例 2

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

出力例 2

2 2 1 1 1

入力例 3

8 6
6 1
3 4
3 6
2 3
4 1
6 4

出力例 3

4 4 4 4 3 4 2 1