C. Не назначать
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Дерево называется простым, если вес каждого пути, состоящего из одного или двух ребер, является простым числом. Рассматриваются только пути, не посещающие никакую вершину дважды. Весом пути называется сумма весов ребер на пути.

Рассмотрим граф ниже. Он является простым деревом, так как вес любого пути из не более чем двух ребер простой. Например, путь из двух ребер $$$2 \to 1 \to 3$$$ имеет вес $$$11 + 2 = 13$$$, который является простым числом. Другой пример, путь из одного ребра $$$4 \to 3$$$ имеет вес $$$5$$$, который является простым числом.

Назначьте веса ребрам любым возможным способом таким, что получившееся дерево будет простым. Если такого способа нет, выведите $$$-1$$$. Можно показать, что если существуют способы сделать дерево простым, то существуют и способ, использующий только веса от $$$1$$$ до $$$10^5$$$.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество вершин в дереве.

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

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных, если существует способ корректно назначить веса, выведите $$$n-1$$$ целое число $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \leq a_i \le 10^5$$$), где $$$a_i$$$ обозначает вес, назначенный ребру $$$i$$$. В противном случае выведите $$$-1$$$.

Если существует несколько решений, выведите любое.

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

В первом примере есть только два пути по одному ребру: $$$1 \to 2$$$ и $$$2 \to 1$$$, оба пути имеют вес $$$17$$$ — простое число.

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

Можно показать, что для третьего примера не существует корректного способа назначить веса.