#P18640. Colorful Graph

Colorful Graph

Colorful Graph

题目描述

给定一张包含 NN 个顶点、MM 条边的有向图。顶点编号为 1,…,N1,\ldots,N,边编号为 1,…,M1,\ldots,M。第 ii 条边从顶点 AiA_i 指向顶点 BiB_i。

请为每个顶点选择一种颜色,颜色编号为 1,…,N1,\ldots,N,使下列条件同时成立:

  • 记顶点 ii 的颜色为 cic_i。对于任意满足 1≤i<j≤N1\le i<j\le N 且 ci=cjc_i=c_j 的两个顶点,图中至少存在一条从 ii 到 jj 的有向路径,或一条从 jj 到 ii 的有向路径;两个方向都存在也可以。
  • max⁡{c1,…,cN}\max\{c_1,\ldots,c_N\} 尽可能小。

构造任意一种满足条件的最优染色。

输入格式

N M
A_1 B_1
A_2 B_2
...
A_M B_M

输入仅包含一组数据,所有数均为整数。M=0M=0 时,第一行之后没有边。

输出格式

输出 NN 个整数 c1,c2,…,cNc_1,c_2,\ldots,c_N,表示每个顶点的颜色。存在多种最优染色时,可以输出任意一种。

输出中不需要额外输出颜色数量。

数据范围

  • 1≤N≤7×1031\le N\le7\times10^3。
  • 0≤M≤7×1030\le M\le7\times10^3。
  • 1≤Ai,Bi≤N1\le A_i,B_i\le N,且 Ai≠BiA_i\ne B_i。
  • 对任意 i≠ji\ne j,(Ai,Bi)≠(Aj,Bj)(A_i,B_i)\ne(A_j,B_j)。

图可以包含有向环,也可以不连通。

样例输入 1

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

样例输出 1

2 1 1 2 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