猫头鹰帕西诺一直很喜欢树木——尤其是无权重的有根树木。他喜欢确定他看到的每棵树的直径,即树中任何简单路径的最大长度。
猫头鹰帕西诺的猫头鹰朋友决定向他展示 Tree Generator™ — 一台强大的机器,可以根据他们的描述创建有根树。以 $$$n$$$ 为顶点的根树可以通过长度为 $$$2(n - 1)$$$ 的括号序列来描述,方法如下:找到在根中开始和结束的任何行走,该行走恰好遍历每条边两次 - 一次沿着树向下,然后沿着树向上。然后沿着路径,如果沿树向下有一条边,则写下“(”(左括号),否则写下“)”(右括号)。
下图显示了有根树示例及其描述:
Owl 写下了 $$$n$$$ 顶点根树的描述。然后,他将描述重写了$$$q$$$次。然而,每次他写一个新的描述时,他都会在上次写的描述中选择两个不同的字符,交换它们并写下生成的字符串。他总是确保每一个书面字符串都是对一棵有根树的描述。
帕西诺随后使用 Tree Generator™ 来记录他写下的每个描述。每棵建造的树的直径是多少?
输入
输入的第一行包含两个整数 $$$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$$$),它们标识要交换的两个括号的索引。您可以假设描述会在每次查询后发生更改,并且每次更改后都可以根据描述构建一棵树。
输出
输出 $$$q + 1$$$ 整数 — 每棵构造树的直径,按照其描述被写下来的顺序。
示例
输入 #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
注意
下图显示了第一个示例测试中构建的每个树及其描述: