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$ 个顶点的有根树可用一个长度为 $2(n - 1)$ 的括号序列来描述，方法如下：找到一条从根出发并最终回到根的遍历路径，该路径恰好经过每条边两次——一次向下（朝向叶子方向），一次向上（朝向根方向）。然后沿此路径行进，每当向下经过一条边时写下 “(”（左括号），向上经过时则写下 “)”（右括号）。

下图展示了若干示例有根树及其对应的括号描述：

帕西诺写下了一个含 $n$ 个顶点的有根树的括号描述。随后，他又重写了该描述共 $q$ 次。每次重写时，他都在上一次写出的描述中任选两个不同位置的字符，交换它们，并将所得字符串记录下来。他始终确保每一次写出的字符串都确实对应某个合法的有根树。

接着，帕西诺对每一次写出的描述均使用“树生成器™”构造出对应的树。那么，每一棵所构造出的树的直径分别是多少？

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.

输入的第一行包含两个整数 $n, q$（$3 \le n \le 100\,000$，$1 \le q \le 100\,000$）—— 分别表示树中顶点的个数以及对树描述进行修改的次数。接下来的一行描述初始树——一个长度为 $2(n-1)$ 的字符串，仅由左括号和右括号组成。

接下来的 $q$ 行每行描述一次对树描述的修改，包含两个以空格分隔的整数 $a_i, b_i$（$2 \leq a_i, b_i \leq 2n-3$），表示需交换的两个括号在字符串中的下标。你可以假设每次查询后树描述都会发生变化，并且每次修改后均能根据该描述构造出一棵合法的树。

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

输出 $q + 1$ 个整数——即每棵构造出的树的直径，按其描述被写出的顺序排列。

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

下图展示了第一个示例测试中每棵构造出的树及其描述：