#P18640. Colorful Graph
Colorful Graph
Colorful Graph
题目描述
给定一张包含 个顶点、 条边的有向图。顶点编号为 ,边编号为 。第 条边从顶点 指向顶点 。
请为每个顶点选择一种颜色,颜色编号为 ,使下列条件同时成立:
- 记顶点 的颜色为 。对于任意满足 且 的两个顶点,图中至少存在一条从 到 的有向路径,或一条从 到 的有向路径;两个方向都存在也可以。
- 尽可能小。
构造任意一种满足条件的最优染色。
输入格式
N M
A_1 B_1
A_2 B_2
...
A_M B_M
输入仅包含一组数据,所有数均为整数。 时,第一行之后没有边。
输出格式
输出 个整数 ,表示每个顶点的颜色。存在多种最优染色时,可以输出任意一种。
输出中不需要额外输出颜色数量。
数据范围
- 。
- 。
- ,且 。
- 对任意 ,。
图可以包含有向环,也可以不连通。
样例输入 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