회의

비버가 사는 섬이 N개 있고, 각 섬에는 0부터 N − 1까지 번호가 붙어 있다. 이 섬들은 N − 1개의 양방향 다리로 연결되어 있으며, 어떤 섬에서 어떤 섬으로든 다리를 통해 이동할 수 있다. 각 섬에 직접 연결된 다리는 최대 18개이다. 각 섬에는 비버 한 마리가 산다.

때때로 여러 비버가 한 섬에 모여 회의를 연다. 정확히 세 마리의 비버가 모일 때, 그들은 다음 조건을 만족하는 섬에 모인다.

세 비버가 모이기 위해 이동하는 다리 개수의 합을 최소로 하는 섬 (그러한 섬은 유일하게 존재한다).

이 섬은 세 비버 중 한 마리가 사는 섬과 같을 수도 있다.

당신은 N개의 섬이 다리로 어떻게 연결되어 있는지 궁금하다. 섬에 직접 가서 확인할 수는 없으므로, 비버에게 몇 가지 지시를 내리려고 한다. 지시는 다음과 같다.

• 세 섬 u, v, w를 지정하고(0 ≤ u ≤ N − 1, 0 ≤ v ≤ N − 1, 0 ≤ w ≤ N − 1, u ≠ v, u ≠ w, v ≠ w), 섬 u, v, w에 사는 비버가 회의를 열게 한다.
• 그러면 세 비버가 모이는 섬을 확인할 수 있다.

당신은 적은 수의 지시로 섬들이 어떻게 연결되어 있는지 알아내려고 한다.

섬의 개수가 주어졌을 때, 비버와 통신하여 섬들의 연결 상태를 알아내는 프로그램을 작성하라.

• 3 ≤ N ≤ 2 000.
• 0 ≤ Ai < Bi ≤ N − 1 (0 ≤ i ≤ N − 2).
• 어떤 섬에서 어떤 섬으로든 다리를 통해 이동할 수 있다.
• 각 섬에 직접 연결된 다리는 최대 18개이다.

Ai와 Bi (0 ≤ i ≤ N − 2)는 섬 Ai와 Bi가 다리로 직접 연결되어 있음을 나타낸다.