Канонический код дерева

1000 мс · 256 МБ · всё или ничего

Дано корневое дерево с корнем 1. Постройте его канонический код Ахо - Хопкрофта - Ульмана.

Код строится снизу вверх: код листа - (), код вершины - открывающая скобка, затем коды детей, отсортированные лексикографически, затем закрывающая.

Для дерева из корня с двумя листьями код равен (()()), для цепочки из трёх вершин - ((())).

Формат ввода

В первой строке - число $n$ ( $1 \le n \le 2000$ ).

В следующих $n - 1$ строках - рёбра дерева. Корень - вершина 1.

Формат вывода

Выведите канонический код дерева.

Примеры

ввод

3
1 2
1 3

вывод

(()())

ввод

3
1 2
2 3

вывод

((()))

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.