#PU1042. USACO 2020 US Open Contest, Gold — Problem 2. Favorite Colors

    ID: 1607 传统题 文件IO:fcolor 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open20来源:usaco.orgscoring:equal_test_cases拓扑排序

USACO 2020 US Open Contest, Gold — Problem 2. Favorite Colors

USACO 2020 US Open Contest, Gold — Problem 2. Favorite Colors

题目描述

Each of Farmer John's NN cows (1≤N≤2⋅1051\le N\le 2\cdot 10^5) has a favorite color. The cows are conveniently labeled 1…N1\ldots N (as always), and each color can be represented by an integer in the range 1…N1\ldots N. There exist MM pairs of cows (a,b)(a,b) such that cow bb admires cow aa (1≤M≤2⋅1051\le M\le 2\cdot 10^5). It is possible that a=ba=b, in which case a cow admires herself. For any color cc, if cows xx and yy both admire a cow with favorite color cc, then xx and yy share the same favorite color. Given this information, determine an assignment of cows to favorite colors such that the number of distinct favorite colors among all cows is maximized. As there are multiple assignments that satisfy this property, output the lexicographically smallest one (meaning that you should take the assignment that minimizes the colors assigned to cows 1…N1\ldots N in that order).

输入格式

The first line contains NN and MM. The next MM lines each contain two space-separated integers aa and bb (1≤a,b≤N1\le a,b\le N), denoting that cow bb admires cow aa. The same pair may appear more than once in the input.

输出格式

For each ii in 1…N1\ldots N, output the color of cow ii in the desired assignment on a new line.

数据范围

Test cases 2-3 satisfy N,M≤103N,M\le 10^3. Test cases 4-10 satisfy no additional constraints. Problem credits: William Lin and Benjamin Qi

样例

样例 1

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
In the image below, the circles with bolded borders represent the cows with 
favorite color 1.