题目描述

There are $N$ cities in Chelsea's state (numbered starting from 1, which is Chelsea's city), and $M$ bidirectional roads directly connect them. (A pair of cities may even be directly connected by more than one road.) Because of changes in traffic patterns, it may take different amounts of time to use a road at different times of day, depending on when the journey starts. (However, the direction traveled on the road does not matter -- traffic is always equally bad in both directions!) All trips on a road start (and end) exactly on the hour, and a trip on one road can be started instantaneously after finishing a trip on another road.

Chelsea loves to travel and is deciding where to go for her winter holiday trip. She wonders how quickly she can get from her city to various other destination cities, depending on what time she leaves her city. (Her route to her destination may include other intermediate cities on the way.) Can you answer all of her questions?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains three integers: the number $N$ of cities, the number $M$ of roads, and the number $K$ of Chelsea's questions.

$2M$ lines -- $M$ pairs of two lines -- follow. In each pair, the first line contains two different integers x and y that describe one bidirectional road between the x-th city and the y-th city. The second line contains 24 integers $Cost[t]$ ($0 \le t \le 23$) that indicate the time cost, in hours, to use the road when departing at t o'clock on that road. It is guaranteed that $Cost[t]$ $\le$ $Cost[t+1]+1$ ($0 \le t \le 22$) and $Cost[23]$ $\le$ $Cost[0]+1$.

Then, an additional $K$ lines follow. Each contains two integers $D$ and $S$ that comprise a question: what is the fewest number of hours it will take to get from city 1 to city $D$, if Chelsea departs city 1 at $S$ o'clock?

输出格式

For each test case, output one line containing "Case #x: ", where x is the case number (starting from 1), followed by $K$ distinct space-separated integers that are the answers to the questions, in order. If Chelsea cannot reach the destination city for a question, no matter which roads she takes, then output $-1$ for that question.

3
3 3 2
1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 
2 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1
3 3
3 1 2
1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2
3 4
3 3 3
1 2
7 23 23 25 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
1 3
10 11 15 26 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11
2 3
7 29 28 27 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
2 14
3 3
3 21

Case #1: 1 2
Case #2: 1 -1
Case #3: 17 26 13

提示

Limits

$1 \le x, y \le N$.

$1 \le$ all Cost values $\le 50$.

$1 \le D \le N$.

$0 \le S \le 23$.

Small dataset (Test Set 1 - Visible)

$1 \le T \le 100$.

$2 \le N \le 20$.

$1 \le M \le 100$.

$1 \le K \le 100$.

Large dataset (Test Set 2 - Hidden)

$1 \le T \le 5$.

$2 \le N \le 500$.

$1 \le M \le 2000$.

$1 \le K \le 5000$.