22142_TheMiddle

Wind and Zero live in a country consisting of N cities. Wind lives in city X, and Zero lives in city Y. There is exactly one path between any two cities. One day, Wind and Zero want to meet each other. So they decide to meet at the middle of the path between city X and city Y. Now, I want you to tell me where it is.

The first line of the input is a single number T, the number of the test cases of the input. Then T blocks each represent a single test case.

The first line of each block contains one integer N ( 1 ≤ N ≤ 10000 ). Then N-1 lines follow, each one contains two integers a, b, which means there is an edge between city a and city b ( 1 ≤ a, b ≤ N ).

Next line contains a integer M ( 1 ≤ M ≤ 100000 ), which is the number of queries.

Then M lines follow, each one contains two integers x, y, which are the city numbers Wind and Zero live ( 1 ≤ x, y ≤ N ).

For every query, if the middle in the path between city x and city y is located at a city, output the number of that city. If the middle is located at a edge, output two numbers, and the city nearer to city x should output first.

Print a blank line after each test case.

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

4 2
2 4
4