레이팅 미적용농부 존의 소 \(N\)마리(\(1\le N\le 2\cdot 10^5\))에게는 각자 좋아하는 색깔이 있다. 소들은 (여느 때처럼) \(1\ldots N\)으로 번호가 매겨져 있고, 각 색깔은 \(1\ldots N\) 범위의 정수로 나타낼 수 있다.
소 \(b\)가 소 \(a\)를 동경하는 소 쌍 \((a,b)\)가 \(M\)개(\(1\le M\le 2\cdot 10^5\)) 존재한다. \(a=b\)일 수도 있는데, 이 경우 소가 자기 자신을 동경하는 것이다. 임의의 색깔 \(c\)에 대해, 소 \(x\)와 \(y\)가 둘 다 좋아하는 색깔이 \(c\)인 소를 동경한다면, \(x\)와 \(y\)는 같은 색깔을 좋아한다.
이 정보가 주어질 때, 모든 소가 좋아하는 서로 다른 색깔의 수가 최대가 되도록 소들에게 좋아하는 색깔을 배정하시오. 이 성질을 만족하는 배정이 여러 개 있으므로, 사전순으로 가장 작은 것을 출력한다(즉, 소 \(1\ldots N\)의 순서대로 배정되는 색깔을 최소화하는 배정을 택해야 한다).
문제 제공: William Lin, Benjamin Qi
배점
- 테스트 케이스 2-3은 \(N,M\le 10^3\)을 만족한다.
- 테스트 케이스 4-10은 추가 제약이 없다.
문제 제공: William Lin, Benjamin Qi
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 \(M\)개의 줄 각각에 소 \(b\)가 소 \(a\)를 동경함을 나타내는, 공백으로 구분된 두 정수 \(a\)와 \(b\)(\(1\le a,b\le N\))가 주어진다. 같은 쌍이 입력에 여러 번 나올 수 있다.
\(1\ldots N\)의 각 \(i\)에 대해, 원하는 배정에서 소 \(i\)의 색깔을 한 줄에 하나씩 출력한다.
fcolor.in · 출력을 쓸 파일 fcolor.out9 12
1 2
4 2
5 8
4 6
6 9
2 9
8 7
8 3
7 1
9 4
3 5
3 41
2
3
1
1
2
3
2
3In the image below, the circles with bolded borders represent the cows with
favorite color 1.
