提示: 欢迎访问OurACM平台。
Problem 1419 The Bus Line Query System

Accept: 34    Submit: 124
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

In a city, bus is the most popular vehicle for citizens to go from one place to another. Unfortunately, sometimes one person can not travel from one bus station to another directly, because there is no bus line through these two stations. So he had to go to a medial station from the starting station, then changes to a bus which go from this intermedial station to the termination.
loy's hierophant asks him to make a bus line query system. To make the problem clear, we assume that there are N bus stations and M bus lines in the city. In a bus line, the bus passes some bus stations orderly, and it passes a certain bus station at most once. The system will find a best solution for passengers when he inputs the staring station and the terminal station.

Assume that:
(1)When a passenger get on a bus, he should put 1 yuan into the money box, no matter how many stations does he take.
(2)It takes a bus 5 minutes to go from one station to the next one. The time the passenger waits for a bus, the time a bus stop in stations and the time the passenger changes buses, can be ignored.

The best solution is defined as follows:

(1)if solution A costs less money than solution B, then solution A is better than solution B.
(2)if solution A costs the same amount of money as solution B, but solution A costs less time than solution B, then solution A is better than solution B.

Input

The first line of the input contains a single integer T (1 <= T <= 10) which is the number of test cases in the input.Each test case starts with one line containing two integers: N, M (1 <= N <= 100, M<=10,000), N is the number of bus stations and M is the number of bus lines. Then follows M lines, each representing an a bus line. A line contains an interger S (S <= N) which is the number of bus stations this bus line has, followed S interger a1,a2,...,as. The bus lines are bidirectional , it means the bus can run a1->a2->...->an, and also an->...->a2->a1, but neither a1->an nor an->a1 directly.Then an interger Q , the number of queries,is followed. The following Q lines, each line contains two interger p,q, means the starting station and the terminal station the passenger choose.You should find the best solution for the passenger.

Output

Before each test case, output "Case d:",where d is the number of the test case. For each query, Output how much the passenger will spend at least, and how long the passenger will cost to get to the termination if he uses the best solution. If there is no solution to take a passenger from the starting station to the terminal station, you should output "Take a taxi!". Print a blank line between each test cases.

Sample Input

1 5 2 4 1 2 3 4 2 1 3 4 1 4 1 3 1 5 3 2

Sample Output

Case 1: 1 15 1 5 Take a taxi! 1 5

Source

FZU ICPC Preliminary Round 2006

Submit  Back  Status  Discuss