| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3.5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 549 | 84 | 67 | 17.678% |
토마토가 꼭지를 안테나처럼 사용해 연결을 형성하고 끊으며 네트워크를 이룬다는 사실은 잘 알려져 있다. 토마토 간의 연결은 날짜가 바뀌는 순간에만 형성되거나 끊어질 수 있으며, 임의의 두 토마토 사이의 연결 상태는 하루에 두 번 이상 바뀌지 않는다.
토마토 네트워크를 전공한 농부 존은 토마토의 연결 상태와 숙성도의 상관관계를 발견했다. 존의 발견에 따르면, 익은 토마토와 덜 익은 토마토가 하루 간 연결되어 있는다면 덜 익은 토마토는 익은 토마토의 영향을 받아 익게 된다.
끈질긴 연구 끝에 존은 토마토 사이의 연결 상태를 관찰하는 기기를 개발했다. 이 기기를 사용하면 0ドル$일에 어떤 토마토가 익어 있고 어떤 토마토들끼리 연결되어 있는지 알 수 있으며, 임의의 두 토마토 사이의 연결이 언제 형성되고 끊어지는지도 추적할 수 있다.
찬우는 천하제일 코딩대회 출제비를 탈탈 털어 존의 기기와 1ドル$부터 $N$까지의 번호가 하나씩 붙은 토마토 $N$개를 샀지만, 어떤 토마토가 언제 익는지 알아내지 못했다. 찬우가 잘 익은 토마토를 먹을 수 있도록 존의 기기에서 얻은 정보로 각 토마토가 익는 날짜를 계산하는 프로그램을 작성해 주자.
첫째 줄에 토마토의 개수 $N,ドル 0ドル$일에 연결되어 있는 토마토 쌍의 수 $M,ドル 0ドル$일에 익은 토마토의 수 $K,ドル 연결 상태가 변하는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq K \leq N \leq 200,000円;$ 0ドル \leq M, Q \leq 200,000円)$
둘째 줄부터 $M$개의 줄에 걸쳐 서로 다른 토마토들의 초기 연결 상태가 중복 없이 주어진다. 각 줄에는 0ドル$일에 연결되어 있는 두 토마토의 번호 $a,ドル $b$가 공백으로 구분되어 주어진다. $(1 \leq a \lt b \leq N)$
그 다음 줄에는 0ドル$일에 익어 있는 서로 다른 토마토의 번호 $X_1,ドル $X_2,ドル $\dotsm,ドル $X_K$가 공백으로 구분되어 주어진다. $(1 \leq X_i \leq N)$
그 다음 줄부터 $Q$개의 줄에 걸쳐 연결 상태의 변화가 일어나는 순서대로 주어진다. 각 줄에는 날짜 $T$와 두 토마토의 번호 $x,ドル $y$가 공백으로 구분되어 주어진다. $T-1$일에 두 토마토가 연결되어 있었다면 $T$일 0ドル$시부터는 연결이 끊어지고, 연결되어 있지 않았다면 $T$일 0ドル$시부터 두 토마토는 새롭게 연결된다. 주어지는 $(T, x, y)$ 쌍은 모두 다르다. $(1 \leq T \leq 200,000円;$ 1ドル \leq x \lt y \leq N)$
입력으로 주어지는 모든 수는 정수이다.
첫째 줄에 $N$개의 정수를 공백으로 구분하여 출력한다. $i$번 토마토가 영원히 익지 않는다면 $i$번째 정수로 -1을, 언젠가 익는다면 익는 날짜를 출력한다.
10 11 2 8 1 2 6 7 2 3 3 4 4 6 1 3 4 5 3 6 8 9 6 8 4 10 1 5 1 1 2 1 4 10 2 6 8 2 2 9 2 6 7 3 6 8 3 7 9 3 8 9
0 1 1 1 0 2 4 4 3 -1
아래는 각각 0ドル$일, 1ドル$일, 2ドル$일, 3ドル$일, 4ドル$일의 토마토의 연결 상태를 나타낸 그림이다. 해당 날짜에 익어 있는 토마토만 색칠되어 있다. 3ドル$일 이후 연결 상태가 변하지 않기 때문에 10ドル$번 토마토는 영원히 익지 않는다.
6 5 1 0 1 2 3 4 1 4 5 6 2 3 1
0 1 2 1 -1 -1
연결 상태가 변하지 않는다.
5 0 2 4 1 2 1 1 5 1 3 4 3 2 3 3 4 5
0 0 4 4 2
0ドル$일에 연결되어 있는 두 토마토가 없다.
입출력 양이 많으므로 문제지 2-4페이지의 언어 가이드에 있는 빠른 입출력을 사용하는 것을 권장한다.