레이팅 미적용농부 존의 소들이 새로운 댄스 무-브(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\)에 또 일어나는 식으로 총 \(M\)분(\(1\le M\le 10^{18}\)) 동안 반복된다. 다시 말해,
- 분 \(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은 \(M=10^{18}\)을 만족한다.
- 테스트 케이스 11-20에는 추가 제약이 없다.
문제 제공: Chris Zhang
첫째 줄에 정수 \(N\), \(K\), \(M\)이 주어진다. 다음 \(K\)개의 줄 각각에 \((a_1,b_1) \ldots (a_K, b_K)\)(\(1\le a_i
\(N\)개의 줄을 출력한다. \(i\)번째 줄에는 소 \(i\)가 도달하는 서로 다른 위치의 개수를 출력한다.
6 4 7
1 2
2 3
3 4
4 55
4
3
3
3
1After \(7\) minutes, the cows in increasing order of position are \([3,4,5,2,1,6]\).
- Cow \(1\) reaches positions \(\{1,2,3,4,5\}\).
- Cow \(2\) reaches positions \(\{1,2,3,4\}\).
- Cow \(3\) reaches positions \(\{1,2,3\}\).
- Cow \(4\) reaches positions \(\{2,3,4\}\).
- Cow \(5\) reaches positions \(\{3,4,5\}\).
- Cow \(6\) never moves, so she never leaves position \(6\).