27. Тимбилдинг

Тимбилдинг — весёлое сплочающее мероприятие. Коллеги активно участвуют в конкурсах, квестах, вместе преодолевают игровые трудности. Подчас люди так увлекаются, что реорганизовать их для какой-то новой активности довольно сложно. Прямо сейчас ведущему нужно разбить всех коллег на две непустые команды так, чтобы каждые два человека в одной команде хорошо знали друг друга — и это непростая задача.

Вам дан граф, в котором каждому человеку сопоставлена ровно одна вершина. Ребро $(u, v)$ означает, что коллега $u$ хорошо знает коллегу $v$ (и в то же время коллега $v$ хорошо знает коллегу $u$). Проверьте, можно ли разбить вершины графа на два множества требуемым образом, и, если это возможно, выведите любое подходящее разбиение.

В первой строке даны два целых числа $n$ и $m$ ($2 \le n \le 5000$, $0 \le m \le 200000$) — число вершин и число рёбер в графе.

В следующих $m$ строках даны описания рёбер — пары целых чисел $a$ $b$ ($1 \le a, b \le n$, $a \ne b$), означающих наличие ребра между вершинами $a$ и $b$.

Гарантируется, что каждая пара вершин соединена не более чем одним ребром, и что никакая вершина не соединена с собой.

Если разбить вершины требуемым образом нельзя, выведите $-1$.

Иначе в первой строке выведите число $k$ ($1 \le k \lt n$) — количество вершин в одной из частей разбиения.

В следующей строке выведите $k$ чисел — вершины из этой части разбиения.

В следующей строке выведите $n - k$ чисел — вершины из второй части разбиения.

Каждая вершина должна принадлежать ровно одной из этих частей.