Дано дерево из \(n\) вершин. Вам необходимо расставить на его ребрах целые неотрицательные числа таким образом, чтобы выполнялось условие:
Для каждых двух вершин \(i\), \(j\) посмотрим на путь между ними и посчитаем сумму чисел на ребрах этого пути. Выпишем полученную сумму на доску. Тогда каждое число от \(1\) до \(\lfloor \frac{2n^2}{9} \rfloor\) должно быть выписано по крайней мере один раз.
Гарантируется, что такая расстановка существует.
Выходные данные
Выведите \(n-1\) строку, каждую вида \(u\) \(v\) \(x\) (\(0 \le x \le 10^6\)), что будет означать, что вы записали число \(x\) на ребре между \(u\), \(v\).
Множество ребер \((u, v)\) должно совпадать с множеством ребер начального графа, но выводить ребра вы можете в любом порядке. Также вы можете выводить концы ребра в порядке, отличном от указанного во входных данных.
Примечание
В первом примере, расстояние между вершинами \(1\) и \(2\) равно \(2\), между \(2\) и \(3\) равно \(1\), между \(1\) и \(3\) равно \(3\).
В третьем примере, числами от \(1\) to \(9\) (включительно) будут выписаны на доску, в то время как достаточно и от \(1\) до \(5\), чтобы пройти тест.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3
2 1
|
3 2 1
1 2 2
|
|
2
|
4
2 4
2 3
2 1
|
4 2 1
3 2 2
1 2 3
|
|
3
|
5
1 2
1 3
1 4
2 5
|
2 1 1
5 2 1
3 1 3
4 1 6
|