- Описание
- Отправленные решения
222. Тимбилдинг
Тимбилдинг — весёлое сплочающее мероприятие. Коллеги активно участвуют в конкурсах, квестах, вместе преодолевают игровые трудности. Подчас люди так увлекаются, что реорганизовать их для какой-то новой активности довольно сложно. Прямо сейчас ведущему нужно разбить всех коллег на две непустые команды так, чтобы каждые два человека в одной команде хорошо знали друг друга — и это непростая задача.
Вам дан граф, в котором каждому человеку сопоставлена ровно одна вершина. Ребро $(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$ чисел — вершины из второй части разбиения.
Каждая вершина должна принадлежать ровно одной из этих частей.
Ограничения
Ограничение времени
1 с
Ограничение памяти
256 МБ
Пример 1
3 1
1 2
2
1 2
3
Пример 2
3 0
-1