H

Hello, Mafia

 

Programming contests are now too frequent in Bangladesh. Just 5 years ago, you could participate in only one or two contest per year, but now, there is one in almost every month. Moreover, they are also in different cities around the country. 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.

Contestants 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 spent in the contest, 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 this contest. For that, they will call strike in different cities, and thus, no vehicle enters or leaves 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 through the city, and may have to use a longer route. If they can't use their shortest route, they will surely be late, and thus, cannot attend the contest.

Mafia lords have a list of teams. They will call strike in minimum number of cities, so that these teams are unable attend the contest. There may be more than one set of cities they can call strike to sabotage the contest, in those cases, they will probably choose the one that affects minimum number of cities.

You have some how managed to know about this evil plan. Now, given the list of cities, you have to find the how many cities will be affected by it.

 

Input

Input starts with an integer T(T≤30), the number of test cases.

Each test case starts with two integers N,M(1≤N≤100000, 0≤M≤500000) the number of cities and the number of direct routes between cities. 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 each contain three integers, u, v, t(0≤u, v<N,1≤t≤1000), a route between city u and v that takes 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. Next Q lines each describe a query. Each query starts with an integer K(1≤K≤100), the number of teams in the list, followed by K integers ni (0≤ni<N).

There will be a blank line before each test case.

 

Output

For each test case, output the case number. For each query, output

x possible way(s) to sabotage the contest.
Teams from at least y cities will be late.

Where x is the number of possible ways to sabotage, and y is the minimum number cities, affected by the strike. If sabotaging is not necessary, output

            Will not sabotage.

For formatting details, see the sample output

 

Sample Input

Sample Output

3

 

5 8

0 1 10

0 3 5

0 4 7

1 2 1

1 3 3

2 3 7

2 4 6

3 4 2

2

2 2 4

2 2 3

 

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:

Query 1:

1 possible way(s) to sabotage the contest.

Teams from at least 5 cities will be late.

Query 2:

2 possible way(s) to sabotage the contest.

Teams from at least 3 cities will be late.

Case 2:

Query 1:

3 possible way(s) to sabotage the contest.

Teams from at least 3 cities will be late.

Case 3:

Query 1:

Will not sabotage.

Problemsetter: Manzurur Rahman Khan, Special Thanks: Jane Alam Jan