Competitions
ADA Training CP
Tree
A weighted tree is given. Find the distance between two given vertices.
Input data
The first line contains the number of nodes n~(1 \le n \le 150000) in the tree. The nodes are numbered from 0 to n - 1. Each of the next n - 1 lines contains three integers u, v, w that correspond to an edge with weight w~(0 \le w \le 1000), connecting nodes u and v. The next line contains the number of queries m~(1 \le m \le 75000). In each of the next m lines there are two integers.
Output data
For each query print the distance between the nodes with the given numbers.
Examples
Input example #1
3 1 0 1 2 0 1 3 0 1 0 2 1 2
Output example #1
1 1 2