Balance by Elimination

Time limit3sMemory limit2048 MB

Summary

Given a binary tree, the task is to remove at most one leaf so the tree becomes height-balanced, and print the leaf or report balanced or impossible.

Level: Medium6 of 10
Topics: Tree, DFS, Greedy
Solved: No attempts yet

Problem

You are given a binary tree with $n$ nodes, numbered from $1$ to $n$ . Node $1$ is the root.

The height of the subtree rooted at node $u$ is $h_u = 1 + \max(h_{\text{left child}}, h_{\text{right child}})$ . If a child does not exist, its subtree height is $0$ . A leaf has height $1$ .

A node is height-balanced if $|h_{\text{left child}} - h_{\text{right child}}| < 2$ . A binary tree is height-balanced if every node is height-balanced.

Remove at most one leaf so that the tree becomes height-balanced, or report that this is impossible. For example, the tree in the second sample (Figure B.1) becomes balanced after removing node $5$ .

Input

The first line contains a single integer $n$ ( $1 \le n \le 10^5$ ), the number of nodes. Then $n$ lines follow. The $i$ -th line contains the labels of the left and right child of node $i$ . A missing child is written as $0$ . The input is guaranteed to be a binary tree.

Output

If the tree is already balanced, print "balanced". If it cannot be made height-balanced, print "impossible". Otherwise, print the number of the leaf to remove.

Hint

Figure B.1: Visualization of Sample Input 2.

Examples3

Example 1
Input
```
4
4 2
0 0
0 0
0 3
```
Expected output
```
balanced
```
Example 2
Input
```
5
2 3
0 0
0 4
0 5
0 0
```
Expected output
```
5
```
Example 3
Input
```
4
2 0
3 0
4 0
0 0
```
Expected output
```
impossible
```