In a remote island kingdom, there are N cities connected by (N-1) bidirectional roads, forming a vast network where each road has a length of 1 unit. The cities are numbered from 1 to N, and the central marketplace, “QuickMart,” is located in city 1. The citizens rely heavily on QuickMart for their daily supplies, but a rebel group threatens to disrupt deliveries by blocking key roads.
A young engineer named Aryan works for QuickMart, tasked with developing a system that ensures timely deliveries. However, with the looming threat of road blockages, Aryan’s goal is to identify which cities become unreachable when a specific road is blocked by the rebels. For the cities that remain connected to city 1, Aryan must calculate the maximum distance that goods will have to travel from the marketplace to the farthest city.
For each of the Q roadblock scenarios, help Aryan find the maximum delivery distance for the cities still connected to city 1.
The next N-1 lines contains two space separated integers u and v denoting the edges of a tree.
Next Q lines contains two space separated integers x and y denoting the blocked path.
Constraints
1 ≤ N ≤ 105
1 ≤ Q ≤ 105
1 ≤ u, v ≤ N
1 ≤ x, y ≤ N
5 2
1 2
1 3
2 4
2 5
1 2
2 5
Sample Output
1 2
Explanation
Geekland looks like:
1
/ \
2 3
/ \
4 5
Query 1: the road connecting (1,2)
is blocked. Only people living in
city 1 and 3 can place delivery orders.
For city 1, distance = 0.
For city 3, distance = 1.
Maximum (city 1, city 3) = 1
Query 2: The road connecting
(2, 5) is blocked. Only people living in
city 1, 2, 3 and 4 can place delivery orders.
For city 1, distance = 0.
For city 2, distance = 1.
For city 3, distance = 1.
For city 4, distance = 2.
A maximum distance of 2 has to be travelled
for people of city 4. 1 -> 2 -> 4