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