Tree Generator™

2000ms

262144K

Description:

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:

$\text{[math]}$

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?

Input:

The first line of the input contains two integers $$$n, q$$$ ($$$3 \le n \le 100\,000$$$, $$$1 \le q \le 100\,000$$$) — the number of vertices in the tree and the number of changes to the tree description. The following line contains a description of the initial tree — a string of length $$$2(n-1)$$$ consisting of opening and closing parentheses.

Each of the following $$$q$$$ lines describes a single change to the description and contains two space-separated integers $$$a_i, b_i$$$ ($$$2 \leq a_i, b_i \leq 2n-3$$$) which identify the indices of two brackets to be swapped. You can assume that the description will change after each query, and that after each change a tree can be constructed from the description.

Output:

Output $$$q + 1$$$ integers — the diameter of each constructed tree, in the order their descriptions have been written down.

Sample Input:

5 5
(((())))
4 5
3 4
5 6
3 6
2 5

Sample Output:

Sample Input:

6 4
(((())()))
6 7
5 4
6 4
7 4

Sample Output:

Note:

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

$\text{[math]}$

Informação

Provedor Codeforces

Código CF1149C