Problems
In IOI Kingdom, there are N cities numbered from 0 to N−1. These cities are connected by N−1 roads through which you can pass in both directions. You can travel from any city to any other city by passing through some of these roads. for each i (0 ≤ i ≤ N − 2), there is a road of length Di connecting the city Ai and the city Bi.
In IOI Kingdom, there are many companies producing special components. Each company produces only one kind of components. No two companies produce the same kind of components. Each company has at least one factory. Each factory is built in one of the cities. More than one company may have factories in the same city.
Sometimes, a company requires components of another company. Assume the company CA requires the components of the company CB (CA, CB). In this case, they need to transport components from CB to CA. They may transport components from any of the factories of the company CB to any of the factories of the company CA. They need to choose factories appropriately to minimize the distance between factories.
First, the number of cities and the information of roads in IOI Kingdom are given. Then, Q queries are given. Each query is written in the following form: the company CA having S factories in cities X[0], X[1], ..., X[S-1] requires components of the company CB having T factories in cities Y[0], Y[1], ..., Y[T-1]. Write a program which, for each query, returns the minimum distance to transport the components.
Input
The first line contains two space separated integers N, Q, which means there are N cities in IOI Kingdom, and Q queries are given to your program.
The (i + 1)-st line (0 ≤ i ≤ N − 2) of the following (N − 1) lines contains three space separated integers Ai,Bi, Di, which means there is a road of length Di connecting the city Ai and the city Bi.
The information of the j-th query is written from the (3j + 1)-st line to the (3j + 3)-rd line (0 ≤ j ≤ Q − 1) of the following 3Q lines.
The (3j + 1)-st line (0 ≤ j ≤ Q − 1) contains two space separated integers S and T (1 ≤ S ≤ N − 1, 1 ≤ T ≤ N − 1), which means the companies U and V have factories in S and T cities respectively.
The (3j + 2)-nd line (0 ≤ j ≤ Q − 1) contains S space separated integers X[0], ..., X[S-1], which means the company U has factories in the cities X[0], ..., X[S-1].
The (3j + 3)-rd line (0 ≤ j ≤ Q − 1) contains T space separated integers Y[0], ..., Y[T-1], which means the company V has factories in the cities Y[0], ..., Y[T-1].
All input data satisfy the following conditions.
2 ≤ N ≤ 500 000.
1 ≤ Q ≤ 100 000.
0 ≤ Ai ≤ N − 1 (0 ≤ i ≤ N − 2).
0 ≤ Bi ≤ N − 1 (0 ≤ i ≤ N − 2).
1 ≤ Di ≤ 100 000 000 (0 ≤ i ≤ N − 2).
Ai ≠ Bi (1 ≤ i ≤ N − 2).
You can travel from any city to any other city through some of these roads.
For each query, it satisfies the following conditions.
1 ≤ S ≤ N − 1.
0 ≤ X[k] ≤ N − 1 (0 ≤ k ≤ S − 1).
1 ≤ T ≤ N − 1
0 ≤ Y[k] ≤ N − 1 (0 ≤ k ≤ T − 1).
X[0], X[1], ..., X[S-1], Y[0], Y[1], ..., Y[T-1] are different from each other.
Sum of Ss does not exceed 1 000 000.
Sum of Ts does not exceed 1 000 000.
Output
When the program terminates successfully, the sample grader writes to the standard output the values returned by Query one per line.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 15 | N ≤ 5 000, Q ≤ 5 000. |
| #2 | 18 | For each query, S, T ≤ 10 is satisfied. |
| #3 | 67 | There are no additional constraints. |
Example
7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5
12
3
11
These are sample input and sample output of the sample grader.
In the query 0, the company U has factories in the cities 0, 6, and the company V has factories in the cites 3, 4. The distance from the factory of the company V in the city 3 to the factory of the company U in the city 6 is minimum. The minimum distance is 12.
In the query 1, the company U has factories in the cities 0, 1, 3, and the company V has factories in the cites 4, 6. The distance from the factory of the company V in the city 6 to the factory of the company U in the city 1 is minimum. The minimum distance is 3.
In the query 2, the company U has factories in the city 2, and the company V has factories in the city 5. The distance from the factory of the company V in the city 5 to the factory of the company U in the city 2 is minimum. The minimum distance is 11.
You must sign in to write code.