Background

Xiao Z is a smart primary school student. He built a tree using plastic tubes and clay. Each piece of clay is connected to one downward plastic tube; some are connected to two upward plastic tubes, while others are connected to some colored balls.

However, the craft quickly toppled due to imbalance. So Xiao Z consulted his classmate Xiao C. Having read about the principle of balance on a scale in an encyclopedia, Xiao C knows that if, at any piece of clay, the load difference between the two upward tubes exceeds the weight of one ball, the craft will topple. Since the balls are heavy, the weight of the clay and plastic tubes can be ignored.

Because moving balls takes time to dismantle and fix, Xiao C wants to move as few balls as possible to balance the craft. Can you help her?

Problem Description

You are given a binary tree whose leaves have weights. Every internal node has exactly two children. Leaf weights are only $0$ or $1$.

You can perform the following operation any number of times: choose two leaves and swap their weights.

Define the weight of a subtree as the sum of the weights of all leaves in that subtree.

You want to make the difference between the weights of the left and right subtrees at every internal node be at most $1$ by using the operation above.

Find the minimum number of operations needed to achieve this.

Input Format

One line containing a string $T$ that describes the tree in a fully parenthesized form. The character B denotes a colored ball.

Formally, the CFG (context-free grammar) of $T$ is defined as:

<T> := (<T><T>) | (B) | ()

Output Format

Output a single integer: the minimum number of operations required, or output impossible if it is not achievable.

((B)())

0

((((B)(B))((B)()))(B))

impossible

(()(((B)(B))(B)))

1

Hint

Sample Explanation

Constraints

Let $N$ be the length of the string $T$.

• For $15\%$ of the testdata, $N \le 25$.
• For $50\%$ of the testdata, $N \le 250$.
• For $100\%$ of the testdata, $2 \le N \le 5000$.

Translated by ChatGPT 5