← 返回题目列表

Codeforces · 1149/C

C. 树生成器™

中文机器翻译题面 查看原题

猫头鹰帕西诺一直很喜欢树木——尤其是无权重的有根树木。他喜欢确定他看到的每棵树的直径,即树中任何简单路径的最大长度。

猫头鹰帕西诺的猫头鹰朋友决定向他展示 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

注意

下图显示了第一个示例测试中构建的每个树及其描述: