Favorite Colors

题目描述

农夫约翰有 $N$ 头奶牛（$1\le N\le 2\cdot 10^5$），每头奶牛都有一个最喜欢的颜色。 奶牛被方便地编号为 $1\ldots N$（一如既往），每种颜色可以用 $1\ldots N$ 范围内的一个整数表示。 存在 $M$ 对奶牛 $(a,b)$，使得奶牛 $b$ 仰慕奶牛 $a$（$1\le M\le 2\cdot 10^5$）。可能出现 $a=b$ 的情况，此时奶牛仰慕她自己。对于任意颜色 $c$，如果奶牛 $x$ 和 $y$ 都仰慕一头最喜欢颜色为 $c$ 的奶牛，那么 $x$ 与 $y$ 的最喜欢颜色相同。 给定这些信息，请确定一种为奶牛分配最喜欢颜色的方案，使得所有奶牛中不同最喜欢颜色的数量最大。由于满足该性质的方案可能不止一种，请输出字典序最小的方案（即按奶牛 $1\ldots N$ 的顺序，使分配给它们的颜色序列尽量小）。

输入格式

第一行包含 $N$ 和 $M$。 接下来 $M$ 行，每行包含两个用空格分隔的整数 $a$ 和 $b$（$1\le a,b\le N$），表示奶牛 $b$ 仰慕奶牛 $a$。输入中同一对可能出现多次。

输出格式

对于每个 $i$（$1\ldots N$），在新的一行输出所求方案中奶牛 $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 的奶牛。 SCORING: 测试点 2-3 满足 $N,M\le 10^3$。 测试点 4-10 没有额外限制。 题目来源：William Lin 和 Benjamin Qi

标签: USACO|2020|Gold

来源

USACO|2020|Gold