У Ксюши есть домашняя шиншилла, дерево на \(n\) вершинах и огромные ножницы. Деревом называется связный граф без циклов. Сейчас Ксюша сидит на скучном уроке физики и думает над тем, как развлечь своего питомца.
Шиншиллам нравится играть с веточками. Веточкой называется дерево из \(3\) вершин.
Веточка выглядит так. Разрезом называется удаление некоторого (ещё не отрезанного) ребра в дереве. У Ксюши полно свободного времени, поэтому она может себе позволить сделать достаточно разрезов, чтобы дерево распалось на веточки. Другими словами, после нескольких (возможно нуля) разрезов, каждая вершина должна принадлежать ровно одной веточке.
Помогите Ксюше выбрать отрезаемые рёбра или сообщите, что сделать это невозможно.
Выходные данные
Выведите ответ для каждого набора входных данных.
Если искомого способа разрезать дерево не существует, выведите \(-1\).
В противном случае выведите целое число \(k\) — количество отрезаемых рёбер. В следующей строке выведите \(k\) различных целых чисел \(e_i\) (\(1 \le e_i < n\)) — номера отрезаемых рёбер. Если \(k = 0\), выведите вместо этого пустую строку.
Если решений несколько, вы можете вывести любое.
Примечание
Первый набор входных данных в первом тесте.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
9
1 2
4 3
7 9
5 4
4 6
3 2
8 7
1 7
6
1 2
1 3
4 3
1 5
6 1
6
1 2
3 2
3 4
4 5
6 5
5
1 3
5 3
5 2
3 4
|
2
2 8
-1
1
3
-1
|
|
2
|
4
2
1 2
3
1 2
3 1
6
1 2
3 1
3 4
3 5
6 1
9
2 6
6 9
9 1
9 7
1 8
7 3
8 5
4 7
|
-1
0
1
2
2
4 3
|