Kingdom of Equality
There is a kingdom called DomKi. There are N cities and N – 1 bidirectional roads in DomKi. The cities of DomKi are connected to each other in such a way that it forms a [Tree](https://en.wikipedia.org/wiki/Tree_(graph_theory).
Recently a dangerous virus called corona has attacked the kingdom and the people in several cities are affected by the disease COVID-19 (which is caused by the corona virus). The infection of the virus has been declared as an epidemic in DomKi.
As COVID-19 - spreads from person to person in close proximity, similar to other respiratory illnesses, such as the flu, some cities in DomKi are under lockdown to ensure social distancing.
Due to lockdown, some roads also became unavailable to use.
Now there is a group of people who may stay in different cities. For an important issue they all want to meet in a specific city if possible. But there is a strange rule is followed by them. They all want to choose a city in such a way that the selected city is reachable by all of them and everyone has to travel the same distance from their residence city to the selected city through the shortest path.
The distance between two cities in DomKi is the number of roads between them in the shortest path.
Suppose there are 10 cities in DomKi numbered from 1 to 10 and 9 roads shown in the above picture. The number (0 or 1) associated with each road determines whether this road is available or not (Note that, 0 means the road is not available and 1 means available).
Let there is a group consist of 2 people, numbered 4 and 6, wants to meet each other. Then there is a possible set (say S) of 4 different cities they can select to meet which is, S = {2, 1, 3, 7}. The shortest distance from city 4 to each city in S and city 6 to each city in S is identical.
Note that, city 5, 9 and 10 are also same distance away from city 4 and 6 but they are not reachable.
Now the task is to count the size of the set S for a given group of people.
It is to be observed that, a group may consist of 1 people also.
Input
The first line of the input contains a positive integers N, denotes the number of cities in the kingdom.
The next N - 1 lines contains the description of the roads .
Each road is described by three positive integers u, v, k, where u and v denotes two cities which is connected by this road and k denotes the availability of the road (0 or 1).
The next line contains a positive integer Q, denotes the number of query.
Each of the next Q lines will describe a group of people, which is a query to be answered .
Each line will begin with a positive integer gi, which denotes the number of people in the ith group. Then in the same line gi space separated numbers will be given which denotes the cities where the people of this group reside.
Note, that there can be more than one people in each city.
1 ≤ N, Q, u, v ≤ 2 × 105.
u != v.
1 ≤ u, v ≤ N
0 ≤ k ≤ 1.
1 ≤ gi ≤ 2 × 105
Sum of all gi ≤ 2 × 105.
Output
For each query output the size of the set S in a new line which is described in the problem statement.
Samples
| Input | Output |
|---|---|
10 1 2 1 1 3 1 3 7 1 2 4 1 2 6 1 2 5 0 5 9 1 5 10 1 4 8 1 1 2 4 6 | 4 |
Here is the diagram for sample1. | |
| Input | Output |
|---|---|
10 3 8 1 3 2 1 3 7 1 8 6 1 6 5 1 3 10 0 8 4 0 10 1 0 6 9 1 5 4 5 9 2 7 2 4 6 2 3 6 3 2 7 2 1 3 | 1 0 1 5 7 |
Here is the diagram for sample2. | |
