BZPRO
#5569. [Usaco2020 Open]Favorite Colors
内存限制：512 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
FarmerJohn的N头奶牛每头都有一种最喜欢的颜色。
奶牛们的编号为1…N，每种颜色也可以用1…N中的一个整数表示。
存在M对奶牛(a,b)，奶牛b仰慕奶牛a
有可能a=b，此时一头奶牛仰慕她自己。
对于任意颜色c，如果奶牛x和y都仰慕一头喜欢颜色c的奶牛，
那么x和y喜欢的颜色相同。
给定这些信息，求一种奶牛喜欢颜色的分配方案，
使得每头奶牛最喜欢的颜色中不同颜色的数量最大。
由于存在多种符合这一性质的分配方案，
输出字典序最小的（这意味着你应当依次最小化分配给奶牛1…N的颜色)
输入格式
输入的第一行包含N和M。1<=N,M<=2*10^5
以下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
数据范围与提示
BZPRO