33982번 - 모모카와 열차 운행표

넥슨 게임 블루 아카이브(Blue Archive)의 무대가 되는 학원도시 키보토스 내의 모든 열차 운행표는 키보토스 총학생회 소속 행정위원회 교통실장 유라키 모모카의 손을 거치지 않는 것이 없다. 모모카는 매일 명란맛 감자칩을 씹으며 게으름을 피우곤 하지만 모모카 없이는 키보토스 전체 열차가 옴짝달싹 움직이지 못한 채 마비되고 만다!

오늘도 모모카는 눈 깜짝할 새에 열차 운행표를 휘갈겨 만들고서는 소파에 누워 감자칩을 입에 넣으며 농땡이를 피우고 있다. 이제 모모카 아래의 교통관리실 행정원이 모모카표 열차 운행표를 받아 실제로 유효한 운행표인지를 검사하고, 유효하지 않다면 어디가 잘못되었는지를 보고하여야 한다. 만약 운행표의 오류를 잘못 보고한다면 민원이 폭주하거나 열차끼리 대충돌이 일어나는 참사가 발생할 수도 있다! 그러나 모모카와 달리 평범하디 평범한 행정원에게 이러한 검사 작업을 매번 직접 하나하나 비교해 가며 처리하는 건 너무나도 벅찬 일이었다.

불쌍한 행정원과 키보토스의 원활한 교통을 위해 모모카의 열차 운행표가 유효한지 검증하고, 유효하지 않다면 어디가 잘못되었는지 알려주는 프로그램을 작성해 보자. 어른인 당신의 힘이 필요하다!

모모카의 열차 운행표가 유효하기 위해서는 다음 조건을 만족해야 한다.

• 열차 운행표대로 열차를 운행하였을 때
  1. 모든 열차가 주어진 철로를 통해 이동할 수 있어야 한다.
  2. 모든 기차역에 최소 통과 요구 횟수 이상의 열차가 지나야 한다.
  3. 동시에 두 대 이상의 열차가 한 역에 도착하거나 정차하여서는 안 된다.
  4. 한 열차가 같은 역을 두 번 이상 지나서는 안 된다.

모모카의 열차 운행표대로 열차를 운행한다고 가정할 때 각 열차의 움직임은 다음과 같다.

1. 열차 운행표대로 열차 $C$가 $A$역에서 $B$역으로 이동해야 할 때, $A$역과 $B$역을 잇는 철로 $U$가 존재한다면, 열차 $C$는 철로 $U$를 따라 $A$역에서 $B$역으로 이동한다.
2. 열차 운행표대로 열차 $C$가 $A$역에서 $B$역으로 이동해야 할 때, $A$역과 $B$역을 잇는 철로 $U$가 존재하지 않는다면, 열차 $C$는 $A$역에서 무기한 정차한다.
3. 열차 운행표대로 열차 $C$가 $A$역에서 $B$역으로 이동해야 할 때, 열차 $C$가 $B$역을 이미 방문한 상태라도 열차 $C$는 $B$역으로 이동한다.
4. 열차 운행표대로 열차 $C$가 $A$역에서 $B$역으로 이동해야 할 때, $B$역으로 동시에 진입하는 다른 열차가 존재하거나 이미 $B$역에 무기한 정차 중인 다른 열차가 존재한다면, 충돌이 발생한다. 충돌 이후 열차 $C$는 $B$역에 무기한 정차 중인 것으로 간주한다.
5. 열차 운행표대로 열차 $C$가 기점 $A$역에서 출발하고자 할 때, 열차 $C$는 차고지에서 시간 $l$에 $A$역으로 진입한다. 만약 $A$역에 동시에 진입하는 다른 열차가 존재하거나 이미 $A$역에 무기한 정차 중인 다른 열차가 존재한다면, 충돌이 발생한다. 충돌 이후 열차 $C$는 $A$역에 무기한 정차 중인 것으로 간주한다.
6. 열차 운행표대로 열차 $C$가 종점 $B$역을 무사히 충돌 없이 방문하게 될 경우, 열차 $C$는 $B$역을 방문한 후 $B$역을 비우고 차고지로 들어간다.

만약 열차가 열차 운행표대로 기점부터 종점까지 역들을 중복 없이 무사히 방문하고 차고지로 들어갈 수 없으면, 해당 열차의 노선은 유효하지 않은 것이다.

첫째 줄에 키보토스 내의 기차역의 개수 $N$, 기차역 사이를 잇는 철로의 개수 $M$, 열차의 개수 $T$가 공백으로 구분되어 주어진다. $(2 \le N \le 100\,000;$ $1 \le M \le 500\,000;$ $1 \le T \le 100\,000)$

둘째 줄에 각 기차역의 최소 통과 요구 횟수 $p_1, p_2, \cdots, p_N$이 공백으로 구분되어 주어진다. $\left(0 \le p_i \le T\right)$

다음 줄부터 $M$개의 줄에 걸쳐 철로의 정보 $u_i$, $v_i$, $t_i$가 공백으로 구분되어 주어진다. 이는 통과하는 데 $t_i$만큼의 시간이 걸리는, 기차역 $u_i$와 $v_i$를 잇는 양방향 철로가 존재한다는 뜻이다. 두 역을 잇는 철로는 최대 $1$개이다. $(1 \le u_i,v_i \le N;$ $u_i \neq v_i;$ $1 \le t_i \le 100\,000)$

이어서 $T$개의 줄에 걸쳐 전체 열차 운행표가 주어진다. 그중 $i$번째 줄에는 $i$번째 열차의 운행 경로 $k_i$, $l_i$, $s_{i,1}$, $s_{i,2}$, $\cdots$, $s_{i,k}$가 공백으로 구분되어 주어진다. 이는 $i$번째 열차는 총 $k_i$개의 역을 지나게 되며, 시간 $l_i$에 $s_{i,1}$을 기점으로 출발하여 순서대로 $s_{i,2}$, $\cdots$, $s_{i,k-1}$를 거쳐 $s_{i,k}$를 종점으로 도착하게 될 것이라는 뜻이다. $(2 \le k_i \le 10\,000;$ $0 \le l_i \le 100\,000;$ $1 \le s_{i,j} \le N)$

모든 $k_i$의 합은 $500\,000$을 넘지 않으며, 입력으로 주어지는 모든 수는 정수이다.

첫째 줄에 열차 운행표에서 유효한 열차 노선의 개수를 출력한다.

다음 $T$개의 줄에 걸쳐 열차 운행표에 적힌 각 열차의 노선이 유효하면 YES를 출력한다. 유효하지 않다면 각 열차가 처음으로 마주하게 되는 문제를 출력한다. 그 문제가 같은 역을 중복으로 방문하게 되는 경우라면 NO: Duplicate Visit을, 존재하지 않는 철로로 이동해야 하는 경우라면 NO: Edge Absence를, 다른 열차와 충돌하게 되는 경우라면 NO: Collision을 출력한다. 중복 방문과 충돌이 동시에 발생하는 경우 중복 방문을 우선시하여 출력한다.

다음 $T+2$번째 줄에 유효한 열차 노선만을 운행하였을 때 모든 역의 각 최소 통과 요구 횟수를 충족시킬 수 있다면 filled를, 그렇지 않다면 unfilled를 출력한다.