{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eOwl Pacino has always been into trees — unweighted rooted trees in particular. He loves determining the \u003cspan class\u003d\"tex-font-style-it\"\u003ediameter\u003c/span\u003e of every tree he sees — that is, the maximum length of any simple path in the tree.\u003c/p\u003e\u003cp\u003eOwl Pacino\u0027s owl friends decided to present him the Tree Generator™ — a powerful machine creating rooted trees from their \u003cspan class\u003d\"tex-font-style-it\"\u003edescriptions\u003c/span\u003e. An $$$n$$$-vertex rooted tree can be \u003cspan class\u003d\"tex-font-style-it\"\u003edescribed\u003c/span\u003e 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 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(\u003c/span\u003e\" (an opening parenthesis) if an edge is followed down the tree, and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)\u003c/span\u003e\" (a closing parenthesis) otherwise.\u003c/p\u003e\u003cp\u003eThe following figure shows sample rooted trees and their descriptions:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/0f7c69151ffce2eebe5fcaa6e575101e?v\u003d1714170746\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eOwl 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.\u003c/p\u003e\u003cp\u003ePacino then used Tree Generator™ for each description he wrote down. What is the diameter of each constructed tree?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eEach 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.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput $$$q + 1$$$ integers — the diameter of each constructed tree, in the order their descriptions have been written down.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 5\n(((())))\n4 5\n3 4\n5 6\n3 6\n2 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n3\n3\n2\n4\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 4\n(((())()))\n6 7\n5 4\n6 4\n7 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n4\n4\n5\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe following figure shows each constructed tree and its description in the first example test: \u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/dbafba49aa0d7654d6dc868ce3153943?v\u003d1714170746\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}