| Codeforces Round 556 (Div. 1) |
|---|
| Закончено |
Сов Пачино всегда интересовался деревьями — невзвешенными подвешенными деревьями, если быть точным. Он любит определять диаметр каждого дерева, что видит — максимальную длину простого пути в дереве.
Друзья Сова Пачино решили подарить ему Генератор Деревьев™ — мощное устройство, позволяющее создавать деревья по их описанию. Подвешенное дерево из $$$n$$$ вершин может быть описано скобочной последовательностью длины $$$2(n - 1)$$$ следующим образом: рассмотрим любой обход дерева, который начинается и заканчивается в корне, и проходит по каждому ребру ровно два раза — один раз вниз по дереву, другой раз вверх. Затем в порядке пути выпишем «(» (открывающую скобку) если по ребру прошли вниз, и «)» (закрывающую скобку), иначе.
На следующей иллюстрации расположены примеры подвешенных деревьев и их описания:
Сов выписал описание подвешенного дерева из $$$n$$$ вершин. Затем, он изменил его описание $$$q$$$ раз. Каждый раз, когда он выписывал новое описание, он выбирал два разных символа в описании, которое он написал в прошлый раз, менял их местами и записывал полученную строку. Он всегда следил за тем, чтобы каждая записанная строка была описанием подвешенного дерева.
Затем Пачино использовал Генератор Деревьев™ для каждого описания, которое он выписал. Какие диаметры у всех построенных деревьев?
В первой строке записано два целых числа $$$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$$$ целых чисел — диаметр каждого построенного по описанию дерева, в порядке, в котором эти описания выписывались.
5 5 (((()))) 4 5 3 4 5 6 3 6 2 5
4 3 3 2 4 4
6 4 (((())())) 6 7 5 4 6 4 7 4
4 4 4 5 3
На следующей иллюстрации изображены все построенные деревья и их описания из первого примера:
