우리 길을 잃은 걸까? (Small)

결승전은 런던에서 열리는데, 일부는 실수로 마운틴뷰로 갔다. 다행히 마운틴뷰에서 런던까지 가는 무료 셔틀이 있다.

셔틀 노선망은 도시 쌍을 잇는 일방통행 노선 $M$개로 이루어진다. 각 노선마다 출발 도시와 도착 도시는 알지만 정확한 길이는 모른다. $i$번 노선에 대해 아는 것은 그 길이가 $a_i$ 이상 $b_i$ 이하의 정수라는 사실뿐이다.

내가 마운틴뷰(1번 도시)에서 런던(2번 도시)까지 가는 경로를 하나 제안했다. 이 경로가 최단 경로일 가능성이 있는지 확인하라. 가능성이 없다면, 앞선 노선을 모두 제안한 대로 탔다고 할 때 최단 경로의 일부가 절대 될 수 없는 첫 노선의 번호를 구하라.

정확히 말하면 이렇다. 제안한 경로에서 앞의 $k$개 노선을 순서대로 잡는다. 각 노선의 길이를 범위 안의 정수로 정하는 방법 중에서, 그 $k$개 노선을 이 순서대로 지나는 것으로 시작하는 1번 도시에서 2번 도시까지의 최단 경로가 존재하게 만드는 방법이 하나라도 있으면 $k$번째 노선은 검사를 통과한다. 통과하지 못하는 가장 작은 $k$를 찾아 그 노선의 번호를 출력한다. 모든 $k$가 통과하면 대신 Looks Good To Me를 출력한다.

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

내가 제안한 경로는 마운틴뷰 → 파리 → 모스크바 → 런던이다. 길이가 어떻게 정해지든 진짜 최단 경로는 마운틴뷰에서 런던으로 바로 가는 노선이거나 마운틴뷰 → 파리 → 런던이다. 따라서 내 경로의 두 번째 노선인 4번(파리 → 모스크바)이 최단 경로의 일부가 절대 될 수 없는 첫 노선이고, 답은 4이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 양의 정수 $N$, $M$, $P$가 주어진다. $N$은 도시의 수이고 도시에는 1번부터 $N$번까지 번호가 붙는다. $M$은 셔틀 노선의 수, $P$는 내가 제안한 경로에 포함된 노선의 수이다.

이어서 $M$개 줄이 주어진다. $i$번째 줄에는 정수 $u_i$, $v_i$, $a_i$, $b_i$가 주어지며, $u_i$번 도시에서 $v_i$번 도시로 가는 일방통행 노선이 있고 그 길이가 $a_i$ 이상 $b_i$ 이하의 정수라는 뜻이다. 노선의 번호는 입력에 주어진 순서대로 1번부터 $M$번까지이다.

각 테스트 케이스의 마지막 줄에는 서로 다른 정수 $P$개가 주어진다. 내가 타는 노선의 번호를 타는 순서대로 나열한 것이다.

제한

• $1 \le T \le 10$
• $2 \le N \le 20$
• $1 \le M \le 20$
• $1 \le P \le 10$
• $1 \le u_i, v_i \le N$
• $1 \le a_i \le b_i \le 1000000$
• 내가 제안한 경로는 1번 도시에서 시작해 2번 도시에서 끝나는 올바른 경로이다.
• 같은 두 도시를 잇는 노선이 여러 개일 수 있고, 어떤 도시에서 자기 자신으로 가는 노선도 있을 수 있다. 제안한 경로는 같은 도시를 두 번 이상 지날 수 있지만, 같은 노선을 두 번 타지는 않는다.

각 테스트 케이스마다 Case #x: n 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $n$은 1번 도시에서 2번 도시까지의 최단 경로의 일부가 절대 될 수 없는, 내 경로에서 첫 번째 노선의 번호이다. 그런 노선이 없으면 $n$ 자리에 Looks Good To Me를 출력한다.