제거로 균형 맞추기

노드가 $n$개인 이진 트리가 주어진다. 노드는 $1$부터 $n$까지 번호가 매겨져 있으며, 노드 $1$이 루트이다.

노드 $u$를 루트로 하는 서브트리의 높이는 $h_u = 1 + \max(h_{\text{왼쪽 자식}}, h_{\text{오른쪽 자식}})$로 정의한다. 자식이 없으면 그 서브트리의 높이는 $0$이다. 따라서 리프 노드의 높이는 $1$이다.

노드가 높이 균형을 이룬다는 것은 $|h_{\text{왼쪽 자식}} - h_{\text{오른쪽 자식}}| < 2$를 만족한다는 뜻이다. 모든 노드가 높이 균형을 이루면 그 이진 트리는 높이 균형 상태이다.

리프 노드를 최대 하나 제거해서 트리를 높이 균형 상태로 만들거나, 그것이 불가능하다고 보고하라. 예를 들어 두 번째 예제 입력의 트리(그림 B.1)는 노드 $5$를 제거하면 균형이 된다.

첫 줄에 노드의 개수를 나타내는 정수 $n$ ($1 \le n \le 10^5$)이 주어진다. 이어서 $n$개의 줄이 주어지며, $i$번째 줄에는 노드 $i$의 왼쪽 자식과 오른쪽 자식 번호가 주어진다. 자식이 없으면 $0$으로 주어진다. 입력 그래프는 이진 트리임이 보장된다.

트리가 이미 균형 상태이면 "balanced"를 출력한다. 높이 균형 상태로 만드는 것이 불가능하면 "impossible"을 출력한다. 그 외에는 제거할 리프 노드의 번호를 출력한다.

그림 B.1: 예제 입력 2의 시각화.