Wind Chime Rearrangement

You want to buy a gift for your little brother Ike. However, Ike only likes wind chimes whose toys (i.e. the hanging ornaments) can be arranged in a specific order. A wind chime is a decorative object that hangs from the ceiling and is composed of a set of horizontal rods connected by vertical wires. Each rod has two wires attached at its two ends. Each wire connects either to another rod (forming further levels) or to a toy.

The wind chime will satisfy Ike if it meets the following two conditions:

1. All toys are on the same level or the depths of any two toys differ by at most one. (Here, the depth of a toy is defined as the number of rods on the path from the ceiling to that toy.)
2. For any two toys whose depths differ by exactly one, the toy on the left must be lower (i.e. at the deeper level) than the toy on the right.

You are allowed to rearrange the wind chime by performing an operation on any rod: swap the two wires attached to its ends. This operation effectively swaps the entire substructures hanging on the left and right ends of that rod, while the order of hooks on the lower rods remains unchanged.

Your task is to determine the minimum number of swaps required to rearrange a given wind chime so that it satisfies Ike’s conditions. If it is impossible, output -1.

The wind chime is given in a bracket representation. A rod is represented as (A B), where A and B are the representations of the left and right substructures, respectively. A toy is represented by a single character T. The structure is a full binary tree where every rod always has two substructures attached.

Note: The depth of a toy is defined as the number of rods from the ceiling to that toy. The ceiling is above the top rod, so if you parse the tree with an initial rod count of 1 at the root, a toy attached directly to the root has depth 2, a toy attached to a rod under the root has depth 3, etc.

Examples:

• Input: (TT) (a rod with two toys, both at the same depth) – already valid, no swap needed.
• Input: (T(TT)) – the left toy is at a shallower level than the two toys on the right. By swapping the top rod, the order becomes the two deeper toys followed by the shallower one, which satisfies the condition. The minimum number of swaps is 1.
</p>

inputFormat

The input consists of a single line containing a string that describes the wind chime. The string is formed using the characters '(', ')', and 'T'. A rod is represented by a pair of matching parentheses enclosing the representations of its left and right substructures, and a toy is represented by the character 'T'.

You should assume that the input string represents a full binary tree.

outputFormat

Output a single integer representing the minimum number of swap operations required to rearrange the wind chime so that it satisfies Ike’s conditions. If it is impossible, output -1.

sample

TT

0