Counting Nodes on a Path in a Tree

You are given an undirected tree consisting of n nodes and n - 1 edges. The tree is rooted at node 1. For a given set of queries, each asking for two nodes u and v, your task is to determine the number of nodes present on the unique path between these two nodes.

The number of nodes on the path can be computed using the depths of u and v along with the depth of their lowest common ancestor (LCA). The formula is given by:

$\text{nodes} = depth(u) + depth(v) - 2\times depth(\text{LCA}(u,v)) + 1$

It is guaranteed that the given input forms a tree. Read the input from stdin and output your results to stdout.

inputFormat

The first line of the input contains an integer n denoting the number of nodes in the tree.

Each of the following n - 1 lines contains two integers u and v indicating that there is an edge connecting node u and node v.

The next line contains an integer q, the number of queries.

Each of the following q lines contains two integers u and v representing a query to determine the number of nodes on the path between nodes u and v.

outputFormat

For each query, output a single line with an integer representing the number of nodes on the path between nodes u and v.

## sample

5
1 2
1 3
2 4
2 5
3
1 4
4 5
3 5

3
3
4

</p>