D. Почти все
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$n$$$ вершин. Вам необходимо расставить на его ребрах целые неотрицательные числа таким образом, чтобы выполнялось условие:

Для каждых двух вершин $$$i$$$, $$$j$$$ посмотрим на путь между ними и посчитаем сумму чисел на ребрах этого пути. Выпишем полученную сумму на доску. Тогда каждое число от $$$1$$$ до $$$\lfloor \frac{2n^2}{9} \rfloor$$$ должно быть выписано по крайней мере один раз.

Гарантируется, что такая расстановка существует.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество вершин.

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), обозначающие что между вершинами $$$u$$$ и $$$v$$$ есть ребро. Гарантируется, что данные ребра образуют дерево.

Выходные данные

Выведите $$$n-1$$$ строку, каждую вида $$$u$$$ $$$v$$$ $$$x$$$ ($$$0 \le x \le 10^6$$$), что будет означать, что вы записали число $$$x$$$ на ребре между $$$u$$$, $$$v$$$.

Множество ребер $$$(u, v)$$$ должно совпадать с множеством ребер начального графа, но выводить ребра вы можете в любом порядке. Также вы можете выводить концы ребра в порядке, отличном от указанного во входных данных.

Примеры
Входные данные
3
2 3
2 1
Выходные данные
3 2 1
1 2 2
Входные данные
4
2 4
2 3
2 1
Выходные данные
4 2 1
3 2 2
1 2 3
Входные данные
5
1 2
1 3
1 4
2 5
Выходные данные
2 1 1
5 2 1
3 1 3
4 1 6
Примечание

В первом примере, расстояние между вершинами $$$1$$$ и $$$2$$$ равно $$$2$$$, между $$$2$$$ и $$$3$$$ равно $$$1$$$, между $$$1$$$ и $$$3$$$ равно $$$3$$$.

В третьем примере, числами от $$$1$$$ to $$$9$$$ (включительно) будут выписаны на доску, в то время как достаточно и от $$$1$$$ до $$$5$$$, чтобы пройти тест.