게임

앨리스와 밥은 N개의 방과 이 방들을 연결하는 통로들로 이루어진 미로에서 게임을 하려고 한다.

미로의 방에는 1, 2, ···, N의 번호가 붙어 있다. 미로의 어떤 방들은 출구를 가지고 있는데, i (1 ≤ i ≤ N)번 방에는 Aᵢ = 1이면 출구가 있고, Aᵢ = 0이면 없다.

미로를 연결하는 통로는 정확히 M쌍의 방 중 하나의 쌍을 연결한다. 같은 쌍의 방을 잇는 통로가 여러 개 존재할 수 있다.

구체적으로는, 각 i (1 ≤ i ≤ M)에 대하여, aᵢ번 방과 bᵢ번 방을 잇는 서로 다른 통로가 cᵢ개 존재한다.

임의의 두 방 사이를 통로들을 통해 오갈 수 있음이 보장되지 않음에 유의하라.

앨리스와 밥은 총 Q번의 게임을 하려고 하는데, j (1 ≤ j ≤ Q)번째 게임은 다음과 같이 진행된다.

• 앨리스가 미로의 sⱼ번 방으로 들어간다.
• 앨리스는 다음 규칙에 따라 인접한 방으로 이동할 수 있다.
• 앨리스가 현재 x번 방에 있다고 하자.
앨리스는 x번 방과 연결된 kⱼ개의 서로 다른 통로를 고른다. 이때 같은 방을 연결하는 여러 통로를 동시에 고를 수 있다. 만약 x번 방과 연결된 통로의 수가 kⱼ보다 작아 서로 다른 kⱼ개의 통로를 고르는 것이 불가능할 경우, 이동할 수 없다.
• 앨리스가 선택을 마친 후 밥은 앨리스가 고른 kⱼ개의 통로 중 하나를 고른다.
• 앨리스는 밥이 고른 통로가 있는 반대쪽 방으로 이동한다.
• 앨리스가 위 규칙에 따라 다른 방으로 이동하는 것을 0번 이상 반복하여 출구가 있는 방에 도달하면 승리한다.

sⱼ번 방에 출구가 있는 경우, 게임이 시작할 때 앨리스가 있는 방에 출구가 있으므로 앨리스가 승리할 수 있음에 유의하라.

앨리스는 자신이 승리하기 위해서 최선을 다하며, 밥 역시 앨리스가 승리하지 못하게 하기 위해 최선을 다한다. 즉, 게임 중 밥이 어떤 선택을 하더라도 앨리스가 매 순간 적절한 선택을 하여 항상 출구가 있는 방에 도달할 수 있다면 앨리스가 승리하고, 그렇지 않으면 승리할 수 없다.

각 게임에 대해, 앨리스가 게임에서 승리할 수 있을지 아닐지를 판정하라.

• 주어지는 모든 수는 정수이다.
• 1 ≤ N ≤ 200000
• 0 ≤ M ≤ 400000
• 1 ≤ Q ≤ 200000
• 정수 i (1 ≤ i ≤ N)에 대하여, Aᵢ는 0 또는 1이다.
• 정수 i (1 ≤ i ≤ M)에 대하여 1 ≤ aᵢ < bᵢ ≤ N
• 서로 다른 두 정수 i, j (1 ≤ i, j ≤ M)에 대하여, aᵢ ≠ aⱼ 또는 bᵢ ≠ bⱼ이다.
• 정수 i (1 ≤ i ≤ M)에 대하여 1 ≤ cᵢ ≤ 1000000000
• 정수 j (1 ≤ j ≤ Q)에 대하여 1 ≤ sⱼ ≤ N
• 정수 j (1 ≤ j ≤ Q)에 대하여 1 ≤ kⱼ ≤ 1000000000000000000

첫 줄에 미로의 방의 수를 나타내는 정수 N, 통로 종류의 수를 나타내는 정수 M, 앨리스와 밥이 진행할 게임의 수를 나타내는 정수 Q가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 N개의 정수 A₁, A₂, ···, Aₙ이 공백으로 구분되어 차례대로 주어진다.

그다음 M개의 줄에 걸쳐, 통로에 대한 정보가 주어진다. 이 중 i (1 ≤ i ≤ M)번째 줄에는 세 정수 aᵢ, bᵢ, cᵢ가 공백으로 구분되어 차례대로 주어진다. 이는 미로에 aᵢ번 방과 bᵢ번 방을 연결하는 cᵢ개의 통로가 있음을 의미한다.

그다음 Q개의 줄에 걸쳐, 앨리스와 밥이 진행할 Q번의 게임에 대한 정보가 주어진다. 이 중 j (1 ≤ j ≤ Q)번째 줄에는 두 정수 sⱼ와 kⱼ가 공백으로 구분되어 차례대로 주어진다.

첫 줄부터 Q개의 줄에 걸쳐, 답을 출력한다. 이 중 j (1 ≤ j ≤ Q)번째 줄에는 j번째 게임에 대하여 앨리스가 승리할 수 있다면 YES, 그렇지 않다면 NO를 출력해야 한다.

anthony0506 작성

출처 KOI