Вам дано дерево из \(n\) вершин, пронумерованных от \(1\) до \(n\), ребра которого пронумерованы от \(1\) до \(n-1\). Деревом называется связный неориентированный граф без циклов. Вам нужно назначить целочисленный вес каждому ребру дереву так, чтобы в результате получилось простое дерево.
Дерево называется простым, если вес каждого пути, состоящего из одного или двух ребер, является простым числом. Рассматриваются только пути, не посещающие никакую вершину дважды. Весом пути называется сумма весов ребер на пути.
Рассмотрим граф ниже. Он является простым деревом, так как вес любого пути из не более чем двух ребер простой. Например, путь из двух ребер \(2 \to 1 \to 3\) имеет вес \(11 + 2 = 13\), который является простым числом. Другой пример, путь из одного ребра \(4 \to 3\) имеет вес \(5\), который является простым числом.
Назначьте веса ребрам любым возможным способом таким, что получившееся дерево будет простым. Если такого способа нет, выведите \(-1\). Можно показать, что если существуют способы сделать дерево простым, то существуют и способ, использующий только веса от \(1\) до \(10^5\).
Выходные данные
Для каждого набора входных данных, если существует способ корректно назначить веса, выведите \(n-1\) целое число \(a_1, a_2, \dots, a_{n-1}\) (\(1 \leq a_i \le 10^5\)), где \(a_i\) обозначает вес, назначенный ребру \(i\). В противном случае выведите \(-1\).
Если существует несколько решений, выведите любое.
Примечание
В первом примере есть только два пути по одному ребру: \(1 \to 2\) и \(2 \to 1\), оба пути имеют вес \(17\) — простое число.
Второй пример описан в условии задачи.
Можно показать, что для третьего примера не существует корректного способа назначить веса.
Примеры
| № | Входные данные | Выходные данные |
|
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
|