Are We Lost Yet? (Small)

The finals are in London, but a few of us went to Mountain View by mistake. A free shuttle service runs from Mountain View to London, so the trip is still possible.

The shuttle service consists of $M$ one way routes between pairs of cities. For every route you know which city it leaves from and which city it goes to, but you do not know its exact length. All you know about route $i$ is that its length is an integer between $a_i$ and $b_i$, inclusive.

I have suggested one path of routes from Mountain View (city 1) to London (city 2), and you want to check my work. Could my path be a shortest path? If it could not, report the id of the first route on my path that can never be part of a shortest path, assuming every earlier route on my path was taken as suggested.

Stated precisely: take the first $k$ routes of my path, in order. Route $k$ passes the check if there is at least one way to choose an integer length for every route inside its range such that some shortest path from city 1 to city 2 starts with exactly those $k$ routes in that order. Find the smallest $k$ that does not pass and print the id of that route. If every $k$ passes, print Looks Good To Me instead.

For example, suppose the shuttle routes are these.

I suggest the path Mountain View → Paris → Moscow → London. Whatever the lengths turn out to be, the true shortest path is either the direct route from Mountain View to London or the path Mountain View → Paris → London. The second route on my path, route 4 from Paris to Moscow, is the first one that can never be part of a shortest path, so the answer is 4.

The first line of the input has the number of test cases, $T$. Each test case starts with a line holding three positive integers $N$, $M$ and $P$. $N$ is the number of cities, numbered 1 to $N$. $M$ is the number of shuttle routes. $P$ is the number of routes on my path from Mountain View (city 1) to London (city 2).

$M$ lines follow. Line $i$ holds four integers $u_i$, $v_i$, $a_i$ and $b_i$, meaning there is a one way route from city $u_i$ to city $v_i$ whose length is an integer between $a_i$ and $b_i$, inclusive. The routes get the ids 1 to $M$ in input order.

The last line of the test case holds $P$ distinct integers, the ids of the routes I take, in travel order.

Limits

• $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$
• My path is a valid path that starts at city 1 and ends at city 2.
• Two cities can be joined by more than one route, and a route can go from a city back to itself. My path can visit the same city more than once, but it never uses the same route twice.

For each test case print one line in the form Case #x: n, where $x$ is the test case number starting from 1 and $n$ is the id of the first route on my path that can never be part of a shortest path from city 1 to city 2. If there is no such route, print Looks Good To Me in place of $n$.