ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1471. Distance in the Tree

Time limit: 1.0 second
Memory limit: 64 MB
A weighted tree is given. You must find the distance between two given nodes.

Input

The first line contains the number of nodes of the tree n (1 ≤ n ≤ 50000). The nodes are numbered from 0 to n – 1. Each of the next n – 1 lines contains three integers u, v, w, which correspond to an edge with weight w (0 ≤ w ≤ 1000) connecting nodes u and v. The next line contains the number of queries m (1 ≤ m ≤ 75000). In each of the next m lines there are two integers.

Output

For each query, output the distance between the nodes with the given numbers.

Sample

inputoutput
3
1 0 1
2 0 1
3
0 1
0 2
1 2
1
1
2
Problem Author: Dmitry Zhukov
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006