| Codeforces Round 360 (Div. 1) |
|---|
| Закончено |
Недавно Пари и Арий узнали про 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 можно оставить себе (а можно тоже кому-нибудь отдать).
Во втором примере не существует способа раздать вершины так, чтобы удовлетворить и Пари, и Ария.
