题目描述

给你一棵 $n$ 个节点的树，其中一号点填了一个左括号，你需要给其余每个点填上 ( 或 )，使得树上合法括号路径数量最多，保证答案唯一。

输入格式

第一行一个数 $n$。

接下来 $n-1$ 行，每行两个正整数 $x,y$ 表示 $x$ 与 $y$ 有一条边相连。

输出格式

一行一个长度为 $n$ 的括号串。

3
1 2
1 3

())

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n\leq 10^5$。

说明

翻译自 AGM 2022 Qualification Round G Parenthesis。