[알고리즘]acm icpc 부류의 문제-3 성배

실행 시간/메모리 제한

실행 시간: 10000ms, 메모리 제한: 65536KB

문제 설명

성배를 찾으러 떠난 퍼시벌은 긴 모험 끝에 성배가 있는 동굴의 지도를 얻었다.

이 동굴은 여러 개의 방으로 이루어져 있는데, 방들은 복도를 통해 연결되어 있으며, 복도를 통해서는 갈 수 없는 방들도 있다. 다행히도 이 동굴의 어떤 방들에는 마법이 걸려있어서 그 방에서는 특정 주기마다 다른 방으로 순간이동하게 되는데 이를 통해 복도를 통해서는 갈 수 없는 다른 방에 도달할 수 있다. 그러나 이 마법은 너무나도 강력하기 때문에 복도를 통해 방문할 수 있는 방들 중에서는 마법이 걸려있는 방은 단 하나만 존재하며(동굴의 입구에는 마법이 걸려있지 않으며, 성배가 있는 방에는 항상 마법이 걸려있다.), 마법을 통해 다른 방으로 이동한 직후에는 다시 마법을 통해 순간이동되지 않는다. 만약 퍼시벌이 성배가 있는 방에 도달한다면 그 순간 마법을 통해 순간이동되더라도 퍼시벌은 성배를 얻게 된다.

또한 이 동굴에는 성배를 보호하기 위한 함정이 설치되어 있다. 이 함정은 퍼시벌이 한 방에 계속 머물러 있을 경우 작동하게 되므로 퍼시벌은 함정이 작동하지 않게 하기 위해 계속 다른 방으로 이동해야만 한다. 한번 갔던 방에 다시 가는 경우에는 함정이 작동되지 않는다.

동굴 안에는 어떤 알려지지 않은 위험이 있을지 모르기 때문에 퍼시벌은 최단 시간내에 성배를 가지고 나오려고 한다. 당신은 퍼시벌을 도와서 동굴에서 성배를 가지고 나오는데 필요한 최소의 시간을 구해야 한다.

입력 설명

입력은 여러 개의 테스트 케이스로 이루어진다. 입력의 첫 줄에는 테스트 케이스의 개수 T가 들어온다.

각각의 테스트 케이스의 첫 줄에는 방의 개수인 N (2 <= N <= 100), 복도의 개수 K (1 <= K <= N*(N-1)/2), 마법이 걸려있는 방의 개수 M (0 <= M <= N)이 주어진다. 방의 번호는 0부터 N-1까지이며, 동굴의 입구가 0번, 성배가 있는 방의 번호가 N-1 이다.

이후 K줄에 걸쳐서 복도를 통해 연결된 방의 번호의 쌍 Xi, Yi가 주어진다. 방을 이동하는데 걸리는 시간은 항상 1이다.

이후 M줄에 걸쳐서 마법이 걸려있는 방의 번호 Sx, 순간이동되어 이동되는 방의 번호 Dx, 마법이 처음 발동하는 시간 Tx, 마법이 발동하는 주기 Ix 가 주어진다. (0 <= Tx < Ix, 1 <= Ix <= 2^25)

출력 설명

각각의 테스트 케이스에 대해 성배를 찾아 나오는데 필요한 최소의 시간을 출력한다. 만약 성배를 가지고 나올 수 없다면 -1을 출력한다. 퍼시벌이 성배를 가지고 나올 수 있을 때 걸리는 시간은 항상 2^31 미만이다.

예제 입력

1
4 2 2
0 1
2 3
1 2 1 2
3 0 2 4

예제 출력

2