Are We Lost Yet? (Large)

A free shuttle service runs $M$ one way routes between cities. For each route you know which city it leaves and which city it enters, but you do not know its exact length. The length of route $i$ is one integer between $a_i$ and $b_i$, inclusive.

I want to travel from city 1 to city 2, and I have written down the routes I plan to take, in order. My path finding is not as good as yours, so check my work.

Go through the routes of my path from the front. Assume that every earlier route was taken exactly as written. A route is fine if you can pick a length for every route inside its own range and pick a way to continue from the destination city of that route to city 2, so that what I have taken so far is the beginning of a shortest path from city 1 to city 2. Report the number of the first route that is not fine.

For example, take these five routes.

Suppose my path is Mountain View, Paris, Moscow, London, that is routes 2, 4 and 5. Route 2 is fine. If route 2 has length 500 and route 3 has length 400, then Mountain View to Paris to London is 900 while the direct route from Mountain View to London is at most 1000, so a shortest path starts with route 2. Route 4 is not fine. After Paris the trip still has to reach London, and Mountain View to Paris to Moscow to London is at least 1001 while route 1 is at most 1000. The answer is route 4.

The first line holds the number of test cases $T$. The first line of each test case holds three positive integers $N$, $M$ and $P$. $N$ is the number of cities, numbered 1 to $N$. $M$ is the number of routes, and $P$ is the number of routes on the path I wrote down.

Each of the next $M$ lines holds four integers $u_i$, $v_i$, $a_i$, $b_i$. 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 are numbered 1 to $M$ in the order they appear in the input.

The last line holds $P$ distinct integers between 1 and $M$: the numbers of the routes I take, in order.

Limits

• $1 \le T \le 10$
• $2 \le N \le 1000$
• $1 \le M \le 2000$
• $1 \le P \le 500$
• $1 \le u_i, v_i \le N$
• $1 \le a_i \le b_i \le 1000000$
• The path I wrote down 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 start and end at the same city. My path may visit the same city more than once, but it never takes the same route twice.

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