드론 라이트 쇼

윤이와 달구와 포닉스는 2025 UDPC의 개최를 축하하기 위해 드론 라이트 쇼를 선보이기로 했다.

셋은 $1$번부터 $N$번까지 번호가 붙은 $N$개의 드론을 준비했다. 드론은 서버의 명령을 받으면 특정 색깔의 불빛을 내는 기능이 탑재되어 있다. 또한, 드론끼리 무선 연결하여 서로 간에 명령을 전달하는 것도 가능하다.

공연은 다음과 같이 진행된다. 먼저 모든 드론의 불빛 색깔을 $0$으로 설정하고, $M$개의 드론 쌍을 무선 연결한다. 그 다음 모든 드론을 공중에 띄운다. 이때, 드론의 번호가 클수록 더 높게 띄운다. 마지막으로 서버는 $Q$개의 준비된 명령을 순서대로 전송한다.

명령은 두 정수 $d$, $c$로 이루어져 있다. $d$는 위아래 방향을 나타내고, $c$는 색깔을 나타낸다. 명령을 받은 드론은 불빛 색깔을 $c$로 변경한다. 그 다음 연결된 드론 중에서 $d$ 방향에 있는 모든 드론에게 동일한 명령을 전파한다. 전파된 명령을 받은 드론도 동일한 과정을 반복한다.

서버에 준비된 각 명령은 어떤 드론에 전송할지가 정해져 있다. 서버가 명령 하나를 전송하고 나면 명령의 전파가 끝날 때까지 기다린 뒤에 다음 명령을 전송해야 한다.

드론 라이트 쇼가 끝났을 때, 각 드론이 내는 불빛의 색깔은 무엇일까?

첫 번째 줄에 드론의 수 $N$, 무선 연결의 수 $M$, 명령의 수 $Q$가 주어진다. $(1 \le N \le 100\,000; 0\le M \le 300\,000; 1 \le Q \le 100\,000)$

다음 $M$개의 줄에 두 정수 $x$, $y$가 주어진다. $x$번 드론과 $y$번 드론이 무선 연결되어 있음을 나타낸다. 중복된 연결은 주어지지 않는다. $(1 \le x < y \le N)$

다음 $Q$개의 줄에 명령을 나타내는 세 정수 $x$, $d$, $c$가 명령을 전송할 순서대로 주어진다.

• $x$는 서버로부터 명령을 받을 드론의 번호를 나타낸다. $(1 \le x \le N)$
• $d$는 명령의 전파 방향을 나타내며, $1$은 위를, $2$는 아래를 의미한다. $(d \in \{1, 2\})$
• $c$는 명령을 받은 드론이 내야 하는 불빛의 색깔을 나타낸다. $(1 \le c \le 100\,000)$

드론 라이트 쇼가 끝났을 때, $1$번부터 $N$번까지 순서대로 드론이 내는 불빛의 색깔을 공백으로 구분하여 출력한다.