마을

카자흐스탄에는 0번부터 $N-1$번까지 번호가 붙은 작은 마을이 $N$개 있다. 큰 도시도 여러 개 있지만 그 개수는 주어지지 않는다. 작은 마을과 큰 도시를 합쳐 정착지라고 한다.

모든 정착지는 양방향 고속도로로 이루어진 하나의 네트워크로 연결되어 있다. 각 고속도로는 서로 다른 두 정착지를 잇고, 두 정착지를 직접 잇는 고속도로는 많아야 하나다. 임의의 두 정착지 $a$와 $b$에 대해, 같은 고속도로를 두 번 이상 지나지 않고 $a$에서 $b$로 가는 방법은 정확히 하나다.

각 작은 마을은 다른 정착지 하나와만 직접 연결되어 있다. 각 큰 도시는 세 개 이상의 정착지와 직접 연결되어 있다.

모든 고속도로의 길이는 양의 정수다. 두 정착지 사이의 거리는 둘 사이를 이동하는 데 필요한 고속도로 길이 합의 최솟값이다.

큰 도시 $C$에 대해 $r(C)$는 $C$에서 가장 먼 작은 마을까지의 거리다. 모든 큰 도시 가운데 $r(C)$가 가장 작은 도시를 허브라고 한다. $R$은 $r(C)$의 최솟값, 즉 허브에서 가장 먼 작은 마을까지의 거리다.

그림에서 도시 $f$만이 허브이고 $r(f) = 16$이므로 $R = 16$이다. $f$를 제거하면 네트워크는 작은 마을 집합 {0, 1, 10}, {2, 3}, {4, 5, 6, 7}, {8, 9}를 포함한 네 개의 조각으로 나뉜다. 어느 조각도 작은 마을이 $\lfloor 11/2 \rfloor$개를 넘지 않으므로 $f$는 균형 허브다.

허브를 제거하면 네트워크는 여러 연결 조각으로 나뉜다. 각 조각에 들어 있는 작은 마을이 $\lfloor N/2 \rfloor$개 이하이면 그 허브를 균형 허브라고 한다. 큰 도시는 세지 않는다.

$6 \le N \le 110$이다.

서로 다른 두 작은 마을 사이의 거리는 1 이상 1,000,000 이하다.

프로그램이 할 수 있는 질의 횟수는 제한되어 있으며, 그 제한은 부분 문제마다 다르다. 질의 횟수 제한을 넘으면 프로그램은 강제로 종료되고 오답으로 처리된다.