우리 아직 길을 잃은 건가요?

Google Code Jam 결승전이 열릴 때가 되었고, 우리 모두 그곳에 가고 싶다! 안타깝게도 우리 중 몇 명은 실수로 올바른 장소인 영국 런던 대신 Mountain View로 가 버렸다. 하지만 걱정하지 않아도 된다. Mountain View에서 런던까지 무료 Google 셔틀 서비스를 이용할 수 있다!

셔틀 서비스는 도시 쌍을 연결하는 M개의 단방향 노선으로 구성된다. 각 노선이 어느 도시에서 출발하여 어느 도시로 가는지는 알지만, 안타깝게도 이 노선들의 길이가 정확히 얼마인지는 모른다. 대신 각 노선의 길이가 $a_{i}$부터 $b_{i}$까지의 정수 값 중 하나일 수 있다는 것만 안다.

나는 이전에도 Google 셔틀을 여러 번 이용했으므로, Mountain View에서 런던까지 가는 노선 경로를 하나 제안했다. 하지만 당신은 내가 경로를 찾는 능력이 당신만큼 뛰어나지 않을까 걱정되어 내 경로를 확인하고 싶어 한다.

내가 제안한 경로가 Mountain View에서 런던까지 가는 최단 경로일 가능성이 있는가? 그렇지 않다면, 내 경로에서 확실히 최단 경로의 일부가 아닌 첫 번째 셔틀 노선의 ID는 무엇인가(그 이전의 모든 셔틀 노선은 내가 제안한 경로에 따라 이용했다고 가정한다)?

예를 들어 다음과 같은 셔틀 노선 목록이 있다고 하자.

ID | Start City     |  Destination City  |  Shuttle Length
---+----------------+--------------------+----------------
1  | Mountain View  |  London            |  [100, 1000]
2  | Mountain View  |  Paris             |  [500, 5000]
3  | Paris          |  London            |  [400, 600]
4  | Paris          |  Moscow            |  [500, 5000]
5  | Moscow         |  London            |  [1, 10000]

나는 Mountain View -> Paris -> Moscow -> London 경로를 제안한다. 실제 최단 경로는 Mountain View에서 런던으로 가는 직행 노선이거나 Mountain View -> Paris -> London 경로일 수 있다. 이는 내 경로의 두 번째 노선인 (Paris -> Moscow)가 확실히 최단 경로의 일부가 아닌 첫 번째 노선이었다는 뜻이다.

제한

시간 제한: 테스트 세트당 60초. 메모리 제한: 1GB. 1 ≤ T ≤ 10. 1 ≤ $u_{i}$, $v_{i}$ ≤ N. 1 ≤ $a_{i}$ ≤ $b_{i}$ ≤ 1000000.

내가 제안한 경로는 Mountain View(도시 #1)에서 런던(도시 #2)까지 가는 유효한 경로임이 보장된다.

같은 두 도시 사이에 둘 이상의 셔틀 노선이 있을 수 있으며, 한 도시에서 그 도시 자체로 가는 셔틀 노선이 있을 수도 있다. 또한 제안된 경로가 같은 도시를 두 번 이상 방문할 수도 있지만, 같은 셔틀 노선을 두 번 이상 사용하지는 않는다.

작은 데이터 세트(테스트 세트 1 - 공개)

2 ≤ N ≤ 20. 1 ≤ M ≤ 20. 1 ≤ P ≤ 10.

큰 데이터 세트(테스트 세트 2 - 비공개)

2 ≤ N ≤ 1000. 1 ≤ M ≤ 2000. 1 ≤ P ≤ 500.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트는 세 양의 정수 N, M, P가 포함된 줄로 시작한다. N은 전체 도시 수(도시에는 1부터 N까지 번호가 매겨진다), M은 전체 셔틀 노선 수, P는 Mountain View(도시 #1)에서 런던(도시 #2)까지 가는 내 경로에 포함된 셔틀 노선 수를 나타낸다.

이어서 각각 네 정수 $u_{i}$, $v_{i}$, $a_{i}$, $b_{i}$로 구성된 M개의 줄이 주어진다. 각 줄은 도시 $u_{i}$에서 도시 $v_{i}$로 가는 단방향 셔틀 노선이 있으며, 그 길이가 $a_{i}$부터 $b_{i}$까지의 정수 값 중 하나일 수 있음을 나타낸다. 노선에는 입력과 같은 순서로 1부터 M까지 식별자가 부여된다.

이어서 1부터 M까지의 범위에 속하는 서로 다른 P개의 정수로 구성된 줄이 주어진다. 이들은 내가 당신과 함께 이용할 셔틀 노선을 순서대로 나타낸다. 각 정수는 앞의 목록에 있는 노선의 ID이다.

각 테스트 케이스마다 "Case #x: n"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, n은 내 경로에서 Mountain View부터 런던까지의 최단 경로에 포함될 가능성이 전혀 없는 첫 번째 셔틀 노선의 ID이다. 그러한 노선이 없다면 대신 "Looks Good To Me"를 출력한다.