AT_ttpc2022_h.Colorful Graph

给定一个有 $N$ 个顶点和 $M$ 条边的有向图。顶点编号为 $1$ 到 $N$，每条边编号为 $1$ 到 $M$。第 $i$ 条边（$1 \leq i \leq M$）是从顶点 $A_i$ 指向顶点 $B_i$ 的有向边。

你需要用 $1$ 到 $N$ 之间的某种颜色为每个顶点染色。对于顶点 $i$（$1 \leq i \leq N$）的颜色 $c_i$，需满足下列条件：

• 对于任意一组 $(i, j)\ (1 \leq i < j \leq N)$，若 $c_i = c_j$，则必须存在从顶点 $i$ 到顶点 $j$ 或从顶点 $j$ 到顶点 $i$ 的路径（都存在也可以）。

请构造一种染色方案，使得 $\max\{c_1, \ldots, c_N\}$ 尽可能小，并输出一种可行方案。

输入以以下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

请输出一种使 $\max\{c_1, \ldots, c_N\}$ 最小的染色方式。

$c_1$ $c_2$ $\cdots$ $c_N$

注意

本题的内存限制为 $256$ MB。

样例解释 1

由于顶点 $2 \to 5 \to 1 \to 4$ 间存在路径，可将顶点 $1, 2, 4, 5$ 染为同一种颜色。

但顶点 $3, 4$ 之间没有路径，因此至少需要两种颜色。

数据范围

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

由 ChatGPT 5 翻译