Дан неориентированный граф из n вершин и m рёбер. Каждое из рёбер графа изначально покрашено либо в красный, либо в синий цвет. За один ход разрешается выбрать произвольную вершину, и изменить цвета всех инцидентных ей рёбер, то есть все красные рёбра, заканчивающиеся в этой вершине, становятся синими, и наоборот, все синие становятся красными.
Найдите кратчайшую последовательность ходов, после выполнения которой все рёбра графа будут покрашены в один цвет.
Выходные данные
Если не существует способа сделать цвета всех рёбер одинаковыми, то выведите - 1 в единственной строке выходных данных. В противном случае сначала выведите k — минимальное необходимое число ходов, а затем выведите k чисел a1, a2, ..., ak, где ai равняется номеру вершины, выбираемой на i-м ходу.
Если подходящих оптимальных последовательностей несколько, то разрешается вывести любую из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 B
3 1 R
3 2 B
|
1
2
|
|
2
|
6 5
1 3 R
2 3 R
3 4 B
4 5 R
4 6 R
|
2
3 4
|
|
3
|
4 5
1 2 R
1 3 R
2 3 B
3 4 B
1 4 B
|
-1
|