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 翻译