A. NP-трудная задача
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Пари и Арий узнали про NP-трудные задачи, особенно им понравилась задача о минимальном вершинном покрытии.

Пусть нам дан некоторый граф G. Подмножество A его вершин называется вершинным покрытием, если для любого ребра uv хотя бы один его конец лежит в множестве, то есть выполнено или (или оба условия).

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

Они отдали свой граф вам и попросили выбрать два непересекающихся множества вершин A и B, таких что и A и B являются вершинным покрытием, или определить, что сделать это невозможно. Каждая вершина может быть отдана только одному из друзей (а некоторые и вовсе можно не отдавать никому).

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

В первой строке входных данных записаны два числа n и m (2 ≤ n ≤ 100 000, 1 ≤ n, m ≤ 100 000) — количество вершин и количество рёбер в выигранном друзьями графе.

В каждой из следующих m строк записана пара чисел ui и vi (1  ≤  ui,  vi  ≤  n), означающая ненаправленное ребро между вершинами ui и vi. Гарантируется, что в графе отсутствуют петли и кратные рёбра.

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

Если невозможно поделить граф между Пари и Арием, как они этого хотят, то выведите «-1» (без кавычек).

Если же существуют два непересекающихся вершинных покрытия, то выведите их описания. Каждое описание состоит из двух строк. Первая строка должна содержать единственное число k — количество вершин в данном вершинном покрытии, а вторая строка должна содержать k чисел — индексы вершин в покрытии. Обратите внимание, что поскольку m ≥ 1, никакое вершинное покрытие не может быть пустым.

Примеры
Входные данные
4 2
1 2
2 3
Выходные данные
1
2
2
1 3
Входные данные
3 3
1 2
2 3
1 3
Выходные данные
-1
Примечание

В первом примере можно отдать Арию вершину номер 2, а Пари вершины с номерами 1 и 3. Вершину 4 можно оставить себе (а можно тоже кому-нибудь отдать).

Во втором примере не существует способа раздать вершины так, чтобы удовлетворить и Пари, и Ария.