CF1149C Tree Generator™

Owl Pacino has always been into trees — unweighted rooted trees in particular. He loves determining the diameter of every tree he sees — that is, the maximum length of any simple path in the tree. Owl Pacino's owl friends decided to present him the Tree Generator™ — a powerful machine creating rooted trees from their descriptions. An $ n $ -vertex rooted tree can be described by a bracket sequence of length $ 2(n - 1) $ in the following way: find any walk starting and finishing in the root that traverses each edge exactly twice — once down the tree, and later up the tree. Then follow the path and write down "(" (an opening parenthesis) if an edge is followed down the tree, and ")" (a closing parenthesis) otherwise. The following figure shows sample rooted trees and their descriptions: Owl wrote down the description of an $ n $ -vertex rooted tree. Then, he rewrote the description $ q $ times. However, each time he wrote a new description, he picked two different characters in the description he wrote the last time, swapped them and wrote down the resulting string. He always made sure that each written string was the description of a rooted tree. Pacino then used Tree Generator™ for each description he wrote down. What is the diameter of each constructed tree?

N/A

N/A

The following figure shows each constructed tree and its description in the first example test: