Programming contests are now quite frequent in Bangladesh. Just 5 years ago, you could participate in only one or two contests per year, but now, there is one in almost every month. Maybe, someday, you will see contests in every week, or maybe every day.
Due to the schedule of the contests, the contestants are really conscious about optimizing the time spent in traveling. For example, if the contest starts at 9:00AM, they plan to reach contest venue, just before that time, so that, no time is wasted. They will be using various forms of public transportations like bus, train, taxi, rickshaw to reach the contest spot. Bus and train may be used to transport between cities, taxi and rickshaws may be used to move within cities. You will be given all the routes one can use to move between cities. Since, contestants are optimizing their time; they will always take the fastest route possible. Rickshaws and taxis always use the fastest route, so you don't have to be concerned about them.
As the programming contests have become popular, it also caught interest of the mafias as well. They are planning to sabotage the next contest. For that, they will call strike in any city, and thus, no vehicle will enter or leave the city. You can't even use rickshaws and taxi to move in the city during the strike. So, it won't be possible for any team to travel in the city, and may have to use a longer route. If any team can't use their shortest route, they will surely be late, and thus, will not be able to attend the contest.
Mafia lords have a list of teams. They will call strike in a city (exactly one); so that these teams will not be able to attend the contest. There may be more than one option. However, you have somehow managed to know about this evil plan. Now, given the list of teams, you have to find the teams who will be affected by it.
Input
Input starts with an integer T (≤ 6), denoting the number of test cases.
Each test case starts a blank line. Next line contains two integers N, M (1 ≤ N ≤ 105, 0 ≤ M ≤ 5*105) the number of cities and the number of direct routes between cities respectively. Each city is denoted by an integer between 0 and N-1.
The contest is going to be held in city 0. Each of the next M lines contains three integers, u, v, t (0 ≤ u, v < N, u ≠ v, 1 ≤ t ≤ 1000), a route between city u and v thattakes time t. There will be at most one direct route between two cities.
This is followed by an integer Q (1 ≤ Q ≤ 1000), the number of queries. Each of the next Q lines describes a query. Each query starts with an integer K (1 ≤ K ≤ 100), the number of teams in the list, followed by K distinct integers: n1 n2, ..., nk (0 ≤ ni < N) denoting the cities, all teams from these cities should not attend the contest.
Output
For each test case, output the case number in a single line. Then for each query, print a single line, containing a 0 if sabotaging is not necessary. Otherwise print two integers x y, where x denotes the number of cities where they can call strikes and y denotes the number of teams that will surely miss the contest if any of the city is chosen for sabotage.
Sample
| Sample Input | Sample Output |
|---|---|
3 9 10 0 1 10 1 3 5 3 5 10 5 4 5 4 1 20 4 2 10 2 0 40 6 7 7 8 6 8 6 4 30 3 2 8 7 3 5 2 6 2 5 4 6 4 0 1 10 1 2 10 2 3 10 3 4 10 1 2 4 2 3 1 0 1 10 1 1 2 | Case 1: 4 3 1 9 2 7 Case 2: 3 3 Case 3: 0 |
Notes
- Dataset is huge, use faster I/O methods.
- For the 1st query in the first case, as they have to forbid teams from city 7 and 8; they can choose one of the cities from {0, 1, 4, 6}, and if any of them is chosen, teams from cities {6, 7, 8} are sure that they will not be able to attend the contest.