문제
범수가 살고 있는 도시는 N개의 집으로 이루어져 있으며, 이 집들은 정확히 N-1개의 길로 이어져 있습니다.
게다가 놀랍게도, 임의의 두 집 사이는 길들로 왕래가 가능하기까지 합니다. (다시 말하자면, 이 도시는 트리 구조를 이룹니다.)
돈이 많은 괴짜 범수는 집 2개를 사서, 하나는 집으로 쓰고 하나는 별장으로 쓰려고 합니다.
별장과 집은 교통이 편리해야 하기 때문에 너무 멀어서는 안 되며, 별장에서는 집과 다른 느낌을 받아야 하기 때문에 너무 가까워서도 안 됩니다.
결과적으로, 범수는 별장과 집 사이의 거리를 정해 놓았습니다.
여기서 두 집 사이의 거리란, 한 집에서 다른 집으로 곧바로 이동하는 동안 지나는 길의 개수를 뜻합니다.
내집마련은 언제나 신중해야 하기 때문에, 범수는 Q개의 가능성을 생각해 놓고 있습니다.
가능성들은 각각 지을 집 위치와, 집과 별장 사이 거리를 포함하고 있습니다.
하지만 범수는 이 두 정보만으로는 별장의 위치를 고를 수 없어서, 프로그래밍을 잘 한다고 소문난 여러분에게 이것을 부탁했습니다.
여러분은 범수가 적어 놓은 Q개의 가능성에 대해, 각각 별장을 하나씩 추천해 주면 됩니다.
다만 별장과 집 사이 거리는 범수가 적어 놓은 대로여야 합니다.
가능한 별장의 위치가 여러 개일 경우, 그들 중 아무거나 하나만 추천해 줘도 범수는 상관없다고 하네요.
조건을 만족하는 별장의 위치는 늘 하나 이상 있다고 합니다.
입력
첫째 줄에는 도시에 있는 집의 개수인 N이 주어집니다.
다음 N-1개 줄에는 두 수 a, b가 주어집니다. 이는 집 a와 집 b가 길로 이어져 있음을 나타냅니다(a, b≤N).
다음 줄에는 범수가 생각해 놓은 가능성의 개수인 Q가 주어집니다.
다음 Q개 줄에는 범수의 가능성을 나타내는 두 수 w, d가 주어집니다.
w는 범수의 집의 위치, d는 집과 별장 사이 거리입니다(1≤w≤N. 1≤d).
<부분문제의 제약조건>
부분문제 1 : (11점)2≤N≤1,000. Q=1.
부분문제 2 : (17점)2≤N≤100,000. Q=1.
부분문제 3 : (29점)2≤N≤1,000. Q≤1,000.
부분문제 4 : (43점)2≤N≤100,000. Q≤100,000.
출력
예제
11
1 3
2 3
3 4
4 5
7 4
3 6
6 8
6 9
6 10
7 11
5
1 1
10 5
11 4
6 1
3 2
3
11
2
9
5
로그인해야 코드를 작성할 수 있어요.