配点 : 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