Page not loading? Try clicking here.
Placeholder

#1842

성배 1s 256MB

Problems

성배를 찾으러 떠난 아이언맨은 긴 모험 끝에 성배가 있는 동굴의 지도를 얻었다.

이 동굴은 여러 개의 방으로 이루어져 있는데, 방들은 복도를 통해 연결되어 있으며, 복도를 통해서는 갈 수 없는 방들도 있다. 다행히도 이 동굴의 어떤 방들에는 마법이 걸려있어서 그 방에서는 특정 주기마다 다른 방으로 순간이동하게 되는데 이를 통해 복도를 통해서는 갈 수 없는 다른 방에 도달할 수 있게 된다.

그러나 이 마법은 너무나도 강력하기 때문에 복도를 통해 방문할 수 있는 방들 중에서는 마법이 걸려있는 방은 단 하나만 존재하며(동굴의 입구에는 마법이 걸려있지 않으며, 성배가 있는 방에는 항상 마법이 걸려있다.),  마법을 통해 다른 방으로 이동한 직후에는 다시 마법을 통해 순간이동되지 않는다. 

만약 아이언맨​이 성배가 있는 방에 도달한다면 그 순간 마법을 통해 순간이동되더라도 아이언맨​은 성배를 얻게 된다.

 

또한 이 동굴에는 성배를 보호하기 위한 함정이 설치되어 있다. 

이 함정은 아이언맨​이 한 방에 계속 머물러 있을 경우 작동하게 되므로 아이언맨​은 함정이 작동하지 않게 하기 위해  계속 다른 방으로 이동해야만 한다. 한번 갔던 방에 다시 가는 경우에는 함정이 작동되지 않는다. 

동굴 안에는 어떤 알려지지 않은 위험이 있을지 모르기 때문에 은 최단 시간내에 성배를 가지고 나오려고 한다. 

당신은 을 도와서 동굴에서 성배를 가지고 나오는데 필요한 최소의 시간을 구해야 한다.


Input

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

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

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


Output

입력에 대해 성배를 찾아 나오는데 필요한 최소의 시간을 출력한다. 만약 성배를 가지고 나올 수 없다면 -1을 출력한다.

아이언맨이 성배를 가지고 나올 수 있을 때 걸리는 시간은 항상 231 미만이다.


Example

4 2 2

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

You must sign in to write code.