Traveling around the country

Limits: 3 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenik lives in a country with \(n\) cities. There are \(n - 1\) roads in the country, each connecting two cities. All cities are connected by roads in such a way that there is only one route between any two cities.

The capital of the country is the city with number 1. Roads lead from the capital to other cities, from them — even further, and thus a network of cities branching out from the center is formed.

Zenik can travel around the country in two ways:

• Take a marshrutka (minibus) between two cities connected by a road.

• Teleport further from the capital — instantly get to any city that is one level further from the capital than the one he is currently in.

There are \(q\) queries: what is the minimum number of steps Zenik needs to reach Marichka if he is currently in city \(u\), and she is in city \(v\).

Input

The first line gives an integer \(n\) — the number of cities in the country.

The next \(n - 1\) lines contain two integers each — pairs of cities connected by a road.

The next line contains a single integer \(q\) — the number of queries.

The next \(q\) lines contain two integers \(u\) and \(v\) each — the cities where Zenik and Marichka are, respectively.

Output

In \(q\) lines, output the minimum number of steps for Zenik to get from city \(u\) to city \(v\).

Constraints

\(1 \le n, q \le 4 \cdot 10^5\),

\(1 \le u, v \le n\).

Scoring consists of the following blocks:

• 1 point for each example from the statement,

• 27 points: \(n, q \le 1000\),

• 14 points: cities \(u\) and \(v\) are at the same distance from the capital,

• 21 points: city \(u\) is not further from the capital than city \(v\),

• 37 points: no additional constraints.

You will receive the points for a block only if your program passes all tests in that block.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 1 2 1 4 2 3 2 5 4 6 6 7 4 5 7 4 7 7 4 4 4	1 2 2 0

Notes

The country in the example looks like this:

In the first query, Zenik is in city 5, and Marichka is in city 7. Zenik can teleport from city 5 to city 7 in one step, since city 5 is at a distance of 2 from the capital, and city 7 is at a distance of 3.

In the second query, Zenik can take a marshrutka from city 7 to city 6, since there is a road between them, and then from city 6 take a marshrutka to city 4. Here he needs to take 2 actions.