Tree Generator™

题意翻译

$n$个点，$m$个询问。 给你一棵树的括号序列，输出它的直径。 有$m$次询问，每次询问表示交换两个括号，输出交换两个括号后的直径（保证每次操作后都为一棵树） 输出共$m+1$行。 $3 \le n \le 100\,000,1 \le q \le 100\,000$

题目描述

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?

输入输出格式

输入格式

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 $ q + 1 $ integers — the diameter of each constructed tree, in the order their descriptions have been written down.

输入输出样例

输入样例 #1

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

输出样例 #1

4
3
3
2
4
4

输入样例 #2

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

输出样例 #2

4
4
4
5
3

说明

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