Favorite Colors

提交数: 1, 通过率: 100%, 平均分: 100

题目描述:

Farmer John 的 N 头奶牛（1≤N≤2⋅105）每头都有一种最喜欢的颜色。奶牛们的编号为 1…N，每种颜色也可以用 1…N 中的一个整数表示。

存在 M 对奶牛 (a,b)，奶牛 b 仰慕奶牛 a（1≤M≤2⋅105）。有可能a=b，此时一头奶牛仰慕她自己。对于任意颜色 c，如果奶牛 x 和 y 各仰慕一头喜欢颜色 c 的奶牛，那么 x 和 y 喜欢的颜色相同。

给定这些信息，求一种奶牛喜欢颜色的分配方案，使得每头奶牛最喜欢的颜色中不同颜色的数量最大。由于存在多种符合这一性质的分配方案，输出字典序最小的（这意味着你应当依次最小化分配给奶牛 1…N 的颜色）。

输入格式:

输入的第一行包含 N 和 M。

以下 M 行每行包含两个空格分隔的整数 a 和 b（1≤a,b≤N），表示奶牛 b 仰慕奶牛 a。同一对奶牛可能会在输入中多次出现。

输出格式:

对于 1…N 中的每一个 i，用一行输出分配给奶牛 i 的颜色。

样例输入:

9 12
1 2
4 2
5 8
4 6
6 9
2 9
8 7
8 3
7 1
9 4
3 5
3 4

样例输出:

1
2
3
1
1
2
3
2
3

提示:

在下图中，用粗边框圆表示的是最喜欢颜色 1 的奶牛。

1642561562575604832.png

测试点性质：
  • 测试点 2-3 满足 N,M≤103。
  • 测试点 4-10 没有额外限制。
时间限制: 1000ms
空间限制: 256MB

来源: USACO 2020 OPEN Gold