Problem Description

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.

Input Format

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 Format

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

3
1 2
1 3

())

Hint

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。

Translated by ChatGPT 5