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 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.
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