Rain_w Loves Skirt

题号：NC232165
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

There are $n$ shops in the city where rain_w lives. And there are $n-1$ roads connecting these shops, any two shops can reach each other directly or indirectly through these $n-1$ roads. The length of the $i$ -th road is $w_i$ , connecting shops $u_i$ and $v_i$ .

As we all know, rain_w likes to wear skirts. There are $m$ types of skirts, and each shop only sells one kind of skirt. More formally, the $i$ -th shop only sells the $k_i$ -th skirt.It is guaranteed that every type of skirt has at least one shop selling it.

Every skirt has its rarity, the $x$ -th skirt is more rare than $y$ -th skirt if and only if there are fewer shops selling skirt $x$ than $y$ . If the number of shops selling them is the same, then the skirt with the smaller id is more rare.

Every day, Rain_w will choose two types of skirts $(x,y)$ which he wants to buy, (it is guaranteed that $x$ is more rare than $y$ ). Then his mother would send him to a shop which sells $x$ -th skirts as a starting point. After buying skirts in this starting point and putting them on, Rain_w will choose another shop that sells one of these of skirts (means sells $x$ or $y$ ) and walk to it along the shortest path, and then he will go home in his mother's car. Because Rain_w enjoys the feeling of wearing a skirt, he will choose the shop with the longest distance that he needs to walk.

Rain_w' s mother knows rain_w' s thoughts, but she doesn't want the cute rain_w to walk outside for too long in a skirt. Therefore, she will carefully chooses the starting point to minimize the distance rain_w walks.

There are $q$ days. Each day, you will know the two skirts rain_w choose, you need to write a program to help rain_w calculate how long he will walk with skirt that day with his mother's control.

输入描述:

The first line contains two integers  --the number of shops in the city and the number of skirt types.

Then  lines follow, the -th line contains three integers  denoting -th road which connecting two shops.

Then a line follows contains  integers, the -th integer  denoting the -th shop sells -th  skirt.

Then follows an integer  -- the number of days

Then  line follow, the -th line contain two integers , denoting the two types of skirts rain_w chose on the -th day.

输出描述:

Print  lines, the -th line contains an integer denoting how long rain_w will walk with skirt on -th day.

示例1

输入

复制

8 3
1 2 1
2 3 1
3 4 1
4 5 1
3 6 1
6 7 1
7 8 1
1 2 1 2 1 2 1 3
2
2 1
3 2

输出

复制

3
4