Being on a grind for the next hottest summer internship on the market, Sybren decided to solve the valid parentheses problem available on Leetcode in under 10 seconds - and he did!
However, he is serious about his pursuit. Therefore he decided to come up with another problem. Namely, you are given a tree with $$$N$$$ nodes. You must place '(' or ')' on every node. Can you do it in a way such that you maximize the number of pairs of nodes $$$(x, y)$$$ for which the simple path from $$$x$$$ to $$$y$$$ forms a valid parentheses match?
The first line of input contains an integer $$$N(1 \leq N \leq 10^5)$$$, denoting the number of nodes that the tree has. The next $$$N-1$$$ lines of input contain two integers $$$x$$$ and $$$y$$$, denoting that there is an edge between node $$$x$$$ and node $$$y$$$.
Print a string of $$$N$$$ parentheses which maximizes the number of valid paths $$$(x, y)$$$ which form a correct parentheses matching. In case there are multiple solutions, print the lexicographically minimal one. Parenthesis $$$p_i$$$ refers to the one which can be found in node number $$$i$$$.
3 1 2 1 3
())
