레이팅 미적용농부 존의 소들이 새로운 댄스 무-브(mooves)를 뽐내고 있다!
처음에 \(N\)마리의 소(\(2\le N\le 10^5\))가 일렬로 서 있으며, 소 \(i\)는 줄의 \(i\)번째 위치에 있다. 댄스 동작의 순서는 \(K\)개(\(1\le K\le 2\cdot 10^5\))의 위치 쌍 \((a_1,b_1), (a_2,b_2), \ldots, (a_{K},b_{K})\)로 주어진다. 댄스의 매 분 \(i = 1 \ldots K\)마다 줄에서 위치 \(a_i\)와 \(b_i\)에 있는 소들이 자리를 바꾼다. 같은 \(K\)번의 교환이 분 \(K+1 \ldots 2K\)에 다시 일어나고, 분 \(2K+1 \ldots 3K\)에 또 일어나는 식으로 무한히 반복된다. 다시 말해,
- 분 \(1\)에는 위치 \(a_1\)과 \(b_1\)에 있는 소들이 자리를 바꾼다.
- 분 \(2\)에는 위치 \(a_2\)와 \(b_2\)에 있는 소들이 자리를 바꾼다.
- ...
- 분 \(K\)에는 위치 \(a_{K}\)와 \(b_{K}\)에 있는 소들이 자리를 바꾼다.
- 분 \(K+1\)에는 위치 \(a_{1}\)과 \(b_{1}\)에 있는 소들이 자리를 바꾼다.
- 분 \(K+2\)에는 위치 \(a_{2}\)와 \(b_{2}\)에 있는 소들이 자리를 바꾼다.
- 이런 식으로 계속된다.
각 소에 대해, 그 소가 언젠가 서게 되는 줄에서의 서로 다른 위치의 개수를 구하시오.
문제 제공: Chris Zhang
배점
- 테스트 케이스 1-5는 \(N\le 100, K\le 200\)을 만족한다.
- 테스트 케이스 6-10은 \(N\le 2000, K\le 4000\)을 만족한다.
- 테스트 케이스 11-20에는 추가 제약이 없다.
문제 제공: Chris Zhang
첫째 줄에 정수 \(N\)과 \(K\)가 주어진다. 다음 \(K\)개의 줄 각각에 \((a_1,b_1) \ldots (a_K, b_K)\)(\(1\le a_i
\(N\)개의 줄을 출력한다. \(i\)번째 줄에는 소 \(i\)가 도달하는 서로 다른 위치의 개수를 출력한다.
5 4
1 3
1 2
2 3
2 44
4
3
4
1- Cow \(1\) reaches positions \(\{1,2,3,4\}\).
- Cow \(2\) reaches positions \(\{1,2,3,4\}\).
- Cow \(3\) reaches positions \(\{1,2,3\}\).
- Cow \(4\) reaches positions \(\{1,2,3,4\}\).
- Cow \(5\) never moves, so she never leaves position \(5\).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > January > Silver