Competitions

# ADA University - February 12 - LCA

# Tree

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** ≤ **150000**). 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** ≤ **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 print the distance between the nodes with the given numbers.

Input example #1

3 1 0 1 2 0 1 3 0 1 0 2 1 2

Output example #1

1 1 2