드론 라이트 쇼

시간 제한1초메모리 제한1024 MB

요약
명령이 x번 드론의 색을 바꾼 뒤 번호가 더 큰(또는 더 작은) 방향의 연결된 드론으로 전파되기를 반복할 때, Q개 명령 후 모든 드론의 최종 색을 구한다.
난이도

어려움10점 중 8점

유형
그래프, DFS, 구현, 동적 계획법
정답자
아직 제출이 없습니다

문제

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

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

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

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

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

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

입력

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

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

다음 QQ개의 줄에 명령을 나타내는 세 정수 xx, dd, cc가 명령을 전송할 순서대로 주어진다.

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

출력

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

예제3

  1. 예제 1

    입력
    6 7 3
1 3
3 4
3 5
3 6
1 4
2 4
4 5
4 2 10
3 1 20
6 2 30
    예상 출력
    30 10 30 20 20 30

  2. 예제 2

    입력
    5 3 4
1 2
2 4
4 5
3 2 5
1 2 3
2 2 8
5 1 2
    예상 출력
    8 8 5 0 2

  3. 예제 3

    입력
    3 2 4
1 2
2 3
1 1 10
2 2 20
1 1 10
2 1 30
    예상 출력
    10 30 30