Недавно Пари и Арий узнали про NP-трудные задачи, особенно им понравилась задача о минимальном вершинном покрытии.
Пусть нам дан некоторый граф G. Подмножество A его вершин называется вершинным покрытием, если для любого ребра uv хотя бы один его конец лежит в множестве, то есть выполнено 
или 
(или оба условия).
Пари и Арий выиграли на командной олимпиаде чудесный неориентированный граф, и теперь каждый хочет забрать себе множество его вершин, являющееся вершинным покрытием.
Они отдали свой граф вам и попросили выбрать два непересекающихся множества вершин A и B, таких что и A и B являются вершинным покрытием, или определить, что сделать это невозможно. Каждая вершина может быть отдана только одному из друзей (а некоторые и вовсе можно не отдавать никому).
Выходные данные
Если невозможно поделить граф между Пари и Арием, как они этого хотят, то выведите «-1» (без кавычек).
Если же существуют два непересекающихся вершинных покрытия, то выведите их описания. Каждое описание состоит из двух строк. Первая строка должна содержать единственное число k — количество вершин в данном вершинном покрытии, а вторая строка должна содержать k чисел — индексы вершин в покрытии. Обратите внимание, что поскольку m ≥ 1, никакое вершинное покрытие не может быть пустым.
Примечание
В первом примере можно отдать Арию вершину номер 2, а Пари вершины с номерами 1 и 3. Вершину 4 можно оставить себе (а можно тоже кому-нибудь отдать).
Во втором примере не существует способа раздать вершины так, чтобы удовлетворить и Пари, и Ария.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 2
2 3
|
1
2
2
1 3
|
|
2
|
3 3
1 2
2 3
1 3
|
-1
|