범수가 살고 있는 도시는 N개의 집으로 이루어져 있으며, 이 집들은 정확히 N-1개의 길로 이어져 있습니다.

게다가 놀랍게도, 임의의 두 집 사이는 길들로 왕래가 가능하기까지 합니다. (다시 말하자면, 이 도시는 트리 구조를 이룹니다.)

돈이 많은 괴짜 범수는 집 2개를 사서, 하나는 집으로 쓰고 하나는 별장으로 쓰려고 합니다.

별장과 집은 교통이 편리해야 하기 때문에 너무 멀어서는 안 되며, 별장에서는 집과 다른 느낌을 받아야 하기 때문에 너무 가까워서도 안 됩니다.

결과적으로, 범수는 별장과 집 사이의 거리를 정해 놓았습니다.

여기서 두 집 사이의 거리란, 한 집에서 다른 집으로 곧바로 이동하는 동안 지나는 길의 개수를 뜻합니다.

내집마련은 언제나 신중해야 하기 때문에, 범수는 Q개의 가능성을 생각해 놓고 있습니다.

가능성들은 각각 지을 집 위치와, 집과 별장 사이 거리를 포함하고 있습니다.

하지만 범수는 이 두 정보만으로는 별장의 위치를 고를 수 없어서, 프로그래밍을 잘 한다고 소문난 여러분에게 이것을 부탁했습니다.

여러분은 범수가 적어 놓은 Q개의 가능성에 대해, 각각 별장을 하나씩 추천해 주면 됩니다.

다만 별장과 집 사이 거리는 범수가 적어 놓은 대로여야 합니다.

가능한 별장의 위치가 여러 개일 경우, 그들 중 아무거나 하나만 추천해 줘도 범수는 상관없다고 하네요.

조건을 만족하는 별장의 위치는 늘 하나 이상 있다고 합니다.

별장 짓기 timer 1s memory 128MB

별장 짓기 1s 128MB