Description

现在是 Google Code Jam 总决赛的时间了，我们都希望能够到场！不幸的是，我们中的几个人却误打误撞去了 Mountain View，而不是正确的地点伦敦。不过别担心——我们可以乘坐 Google 提供的免费穿梭巴士从 Mountain View 前往伦敦！

这项巴士服务由 $M$ 条单向路线组成，连接着不同的城市。对于每一条路线，你知道它是从哪座城市出发、到达哪座城市，但你并不知道这条路线的具体长度。你只知道每条路线的长度可以是从 $a_i$ 到 $b_i$（包含两端）的任意整数值。

我曾多次乘坐 Google 的穿梭巴士，因此我为你规划了一条从 Mountain View 到伦敦的路线。但你担心我的路径规划能力不如你，所以你想检查一下我的方案。

给定我建议的这条路径，它是否有可能是 Mountain View 到伦敦的最短路径？如果不是，那么请指出在我的路径上第一个肯定不可能属于最短路径的穿梭巴士路线的编号（假设在此之前的所有路线都已按照我建议的路径依次乘坐）。

例如，假设有如下穿梭路线列表：

我建议的路径为 Mountain View -> Paris -> Moscow -> London。实际上，最短路径可能是直接从 Mountain View 到 London，也可能是 Mountain View -> Paris -> London。这意味着我建议的路径上第二段（Paris -> Moscow）就是第一个肯定不可能属于最短路径的穿梭路线。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为三个正整数 $N$、$M$、$P$，分别表示城市总数（城市编号为 $1$ 到 $N$）、穿梭路线总数、以及我建议的路径上穿梭路线的数量（从 Mountain View（城市 $1$）到 London（城市 $2$））。

接下来 $M$ 行，每行四个整数 $u_i$、$v_i$、$a_i$、$b_i$，表示有一条从城市 $u_i$ 到城市 $v_i$ 的单向穿梭路线，其长度可以是 $a_i$ 到 $b_i$ 之间的任意整数。穿梭路线的编号为 $1$ 到 $M$，顺序与输入一致。

接下来一行包含 $P$ 个不同的整数，范围为 $1$ 到 $M$，依次表示我建议的路径上经过的穿梭路线编号。

Output Format

对于每个测试用例，输出一行 "Case #x: n"，其中 $x$ 为测试用例编号（从 $1$ 开始），$n$ 为我的路径上第一个肯定不可能属于最短路径的穿梭路线编号。如果所有路线都有可能属于最短路径，则输出 "Looks Good To Me"。

3
4 5 3
1 2 100 1000
1 3 500 5000
3 2 400 600
3 4 500 5000
4 2 1 10000
2 4 5
3 3 2
1 3 1 1
3 2 1 1
1 2 1 2
1 2
5 6 3
1 3 1 1
4 2 1 9
1 4 1 1
3 5 2 2
5 2 2 2
3 4 1 2
1 6 2

Case #1: 4
Case #2: Looks Good To Me
Case #3: 6

Hint

限制条件

• 我的路径保证是从 Mountain View（城市 $1$）到 London（城市 $2$）的一条合法路径。
• 可能会有多条路线连接同一对城市，也可能有从某城市到自身的路线。建议的路径可能会多次经过同一城市，但不会重复使用同一条路线。

小数据集（12 分，测试集 1 - 可见）

• $2 \leq N \leq 20$
• $1 \leq M \leq 20$
• $1 \leq P \leq 10$

大数据集（18 分，测试集 2 - 隐藏）

• $2 \leq N \leq 1000$
• $1 \leq M \leq 2000$
• $1 \leq P \leq 500$

翻译由 ChatGPT-4.1 完成。