링크 컷 토마토

토마토가 꼭지를 안테나처럼 사용해 연결을 형성하고 끊으며 네트워크를 이룬다는 사실은 잘 알려져 있다. 토마토 간의 연결은 날짜가 바뀌는 순간에만 형성되거나 끊어질 수 있으며, 임의의 두 토마토 사이의 연결 상태는 하루에 두 번 이상 바뀌지 않는다.

토마토 네트워크를 전공한 농부 존은 토마토의 연결 상태와 숙성도의 상관관계를 발견했다. 존의 발견에 따르면, 익은 토마토와 덜 익은 토마토가 하루 간 연결되어 있는다면 덜 익은 토마토는 익은 토마토의 영향을 받아 익게 된다.

끈질긴 연구 끝에 존은 토마토 사이의 연결 상태를 관찰하는 기기를 개발했다. 이 기기를 사용하면 $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을, 언젠가 익는다면 익는 날짜를 출력한다.

입출력 양이 많으므로 문제지 2-4페이지의 언어 가이드에 있는 빠른 입출력을 사용하는 것을 권장한다.