문제
성배를 찾으러 떠난 아이언맨은 긴 모험 끝에 성배가 있는 동굴의 지도를 얻었다.
이 동굴은 여러 개의 방으로 이루어져 있는데, 방들은 복도를 통해 연결되어 있으며, 복도를 통해서는 갈 수 없는 방들도 있다. 다행히도 이 동굴의 어떤 방들에는 마법이 걸려있어서 그 방에서는 특정 주기마다 다른 방으로 순간이동하게 되는데 이를 통해 복도를 통해서는 갈 수 없는 다른 방에 도달할 수 있게 된다.
그러나 이 마법은 너무나도 강력하기 때문에 복도를 통해 방문할 수 있는 방들 중에서는 마법이 걸려있는 방은 단 하나만 존재하며(동굴의 입구에는 마법이 걸려있지 않으며, 성배가 있는 방에는 항상 마법이 걸려있다.), 마법을 통해 다른 방으로 이동한 직후에는 다시 마법을 통해 순간이동되지 않는다.
만약 아이언맨이 성배가 있는 방에 도달한다면 그 순간 마법을 통해 순간이동되더라도 아이언맨은 성배를 얻게 된다.
또한 이 동굴에는 성배를 보호하기 위한 함정이 설치되어 있다.
이 함정은 아이언맨이 한 방에 계속 머물러 있을 경우 작동하게 되므로 아이언맨은 함정이 작동하지 않게 하기 위해 계속 다른 방으로 이동해야만 한다. 한번 갔던 방에 다시 가는 경우에는 함정이 작동되지 않는다.
동굴 안에는 어떤 알려지지 않은 위험이 있을지 모르기 때문에 은 최단 시간내에 성배를 가지고 나오려고 한다.
당신은 을 도와서 동굴에서 성배를 가지고 나오는데 필요한 최소의 시간을 구해야 한다.
입력
입력의 첫 줄에는 방의 개수인
이후 K줄에 걸쳐서 복도를 통해 연결된 방의 번호의 쌍
이후 M줄에 걸쳐서 마법이 걸려있는 방의 번호 Sx, 순간이동되어 이동되는 방의 번호 Dx, 마법이 처음 발동하는 시간 Tx, 마법이 발동하는 주기 Ix 가 주어진다.
출력
입력에 대해 성배를 찾아 나오는데 필요한 최소의 시간을 출력한다. 만약 성배를 가지고 나올 수 없다면 -1을 출력한다.
아이언맨이 성배를 가지고 나올 수 있을 때 걸리는 시간은 항상 231 미만이다.
예제
4 2 2
0 1
2 3
1 2 1 2
3 0 2 4
2
로그인해야 코드를 작성할 수 있어요.