P8235 [AGM 2022 Qualifier] Parentheses

You are given a tree with $n$ nodes. Node $1$ is filled with a left parenthesis. You need to fill each of the remaining nodes with `(` or `)`, so that the number of valid parenthesis paths on the tree is maximized. It is guaranteed that the answer is unique.

The first line contains an integer $n$. The next $n - 1$ lines each contain two positive integers $x, y$, indicating that there is an edge between $x$ and $y$.

Output a parenthesis string of length $n$ in one line.

#### Constraints For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^5$. #### Notes Translated from [AGM 2022 Qualification Round G Parenthesis](https://judge.agm-contest.com/public/problems/5/text)。 Translated by ChatGPT 5