{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\u003cp\u003eYou are a researcher investigating algorithms on binary trees.\nBinary tree is a data structure composed of branch nodes and leaf nodes.\nEvery branch nodes have left child and right child, and each child is either a branch node or a leaf node.\nThe root of a binary tree is the branch node which has no parent.\n\u003c/p\u003e\n\u003cp\u003eYou are preparing for your presentation and you have to make a figure of binary trees using a software.\nYou have already made a figure corresponding to a binary tree which is composed of one branch node and two leaf nodes (Figure 1.)\nHowever, suddenly the function of your software to create a figure was broken.\nYou are very upset because in five hours you have to make the presentation in front of large audience.\n\u003c/p\u003e\n\u003cp\u003eYou decided to make the figure of the binary trees using only copy function, shrink function and paste function of the presentation tool.\nThat is, you can do only following two types of operations.\n\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e\u003cp\u003e Copy the current figure to the clipboard.\u003c/p\u003e\n \u003cul\u003e\u003cli\u003e\u003cp\u003eThe figure copied to the clipboard before is removed.\u003c/p\u003e\u003c/li\u003e\u003c/ul\u003e\n \u003c/li\u003e\n \u003cli\u003e\u003cp\u003e Paste the copied figure (with shrinking, if needed), putting the root of the pasted figure on a leaf node of the current figure.\u003c/p\u003e\n \u003cul\u003e\u003cli\u003e\u003cp\u003e You can paste the copied figure multiple times.\u003c/p\u003e\u003c/li\u003e\u003c/ul\u003e\n \u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003eMoreover, you decided to make the figure using the minimum number of paste operations because paste operation is very time cosuming.\nNow, your job is to calculate the minimum possible number of paste operations to produce the target figure.\n\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/59b54a205cee5ed37d6bed6a57aac161?v\u003d1715981831\" height\u003d\"149\" width\u003d\"178\"\u003e\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003ci\u003eFigure 1: initial state\u003c/i\u003e\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003eFor example, the answer for the instance of sample 1(Figure 4) is 3, because you can produce the target figure by following operations and this is minimum.\n\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/1e62a2c2cae291e5fa44f7e7eb3913c7?v\u003d1715981831\" height\u003d\"192\" width\u003d\"257\"\u003e\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003ci\u003eFigure 2: intermediate 1\u003c/i\u003e\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/591a083dc6a55001e584f95dee82665a?v\u003d1715981831\" height\u003d\"183\" width\u003d\"243\"\u003e\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003ci\u003eFigure 3: intermediate 2\u003c/i\u003e\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/c13212fdc3a7c424cd96e619c3318849?v\u003d1715981831\" height\u003d\"219\" width\u003d\"291\"\u003e\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003ccenter\u003e\u003ci\u003eFigure 4: Goal\u003c/i\u003e\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cp\u003eThe input is a line which indicates a binary tree.\nThe grammar of the expression is given by the following BNF.\n\u003c/p\u003e\n\u003cblockquote\u003e\n\u0026lt;tree\u0026gt; ::\u003d \u0026lt;leaf\u0026gt; | \"(\" \u0026lt;tree\u0026gt; \u0026lt;tree\u0026gt; \")\"\u003cbr\u003e\u0026lt;leaf\u0026gt; ::\u003d \"()\"\u003cbr\u003e\u003c/blockquote\u003e\n\n\u003cp\u003eEvery input obeys this syntax.\n\nYou can assume that every tree in the input has at least 1 branch node, and that it has no more than 10^5 branch nodes.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003eA line containing the minimum possible number of paste operations to make the given binary tree.\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e((()())(((()())(()()))()))\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e3\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e(((()())(()()))(()()))\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e4\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e((()(()()))((()(()()))()))\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e3\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 4\u003c/h2\u003e\n\n\u003cpre\u003e(()())\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 4\u003c/h2\u003e\n\n\u003cpre\u003e0\n\u003c/pre\u003e"}}]}