Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.ArrayDeque

fun main(args: Array<String>) {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))
    
    val (n, m) = reader.readLine().split(" ").map { it.toInt() }
    // Формируем матрицу смежности для исходного графа.
    // Индексы от 1 до n; для i==j оставляем false (нет петель).
    val graph = Array(n + 1) { BooleanArray(n + 1) }
    repeat(m) {
        val (a, b) = reader.readLine().split(" ").map { it.toInt() }
        graph[a][b] = true
        graph[b][a] = true
    }
    
    // Цветов: 0 - не раскрашена, 1 и 2 - разные доли.
    val color = IntArray(n + 1)
    // Используем очередь для BFS.
    val queue = ArrayDeque<Int>()
    
    // Функция противоположного цвета.
    fun opp(c: Int) = if (c == 1) 2 else 1
    
    // Обходим все вершины, выполняем BFS по каждому компоненту в дополнении графа.
    for (u in 1..n) {
        if (color[u] == 0) {
            color[u] = 1
            queue.addLast(u)
            while (queue.isNotEmpty()) {
                val cur = queue.removeFirst()
                // Перебираем все вершины, чтобы найти рёбра в дополнении
                for (v in 1..n) {
                    if (v == cur) continue
                    // Если ребра (cur, v) нет в исходном графе, то в дополнении есть ребро.
                    if (!graph[cur][v]) {
                        if (color[v] == 0) {
                            color[v] = opp(color[cur])
                            queue.addLast(v)
                        } else if (color[v] == color[cur]) {
                            // Если обнаружено противоречие – дополнение не двудольное.
                            writer.write("-1")
                            writer.newLine()
                            writer.flush()
                            reader.close()
                            writer.close()
                            return
                        }
                    }
                }
            }
        }
    }
    
    // Если одна из долей оказалась пустой, необходимо скорректировать.
    // Это возможно только если в дополнении графа нет рёбер в некоторой компоненте (изолированные вершины).
    // Найдём любую вершину и сменим для неё цвет, если одна из групп пуста.
    var count1 = 0
    var count2 = 0
    for (i in 1..n) {
        if (color[i] == 1) count1++ else count2++
    }
    if (count1 == 0 || count2 == 0) {
        // В этом случае весь граф является компонентой без ребер в дополнении (исходный граф – полный)
        // или все вершины изолированы. Просто возьмём одну вершину и переключим её цвет.
        for (i in 1..n) {
            // переключаем цвет одной вершины,
            // проверим: если вершина изолирована в дополнении, то есть для любого j != i, graph[i][j] == true
            var isolated = true
            for (j in 1..n) {
                if (i != j && !graph[i][j]) { // найдена вершина j, с которой нет ребра в исходном графе
                    isolated = false
                    break
                }
            }
            if (isolated) {
                color[i] = opp(color[i])
                break
            }
        }
    }
    
    // Повторно подсчитаем размеры групп
    val group1 = mutableListOf<Int>()
    val group2 = mutableListOf<Int>()
    for (i in 1..n) {
        if (color[i] == 1) {
            group1.add(i)
        } else {
            group2.add(i)
        }
    }
    // Если даже после корректировки одна из групп оказалась пустой (теоретически не должно случиться для двудольного дополнения),
    // то выводим -1.
    if (group1.isEmpty() || group2.isEmpty()) {
        writer.write("-1")
        writer.newLine()
    } else {
        writer.write("${group1.size}")
        writer.newLine()
        writer.write(group1.joinToString(" "))
        writer.newLine()
        writer.write(group2.joinToString(" "))
        writer.newLine()
    }
    
    writer.flush()
    reader.close()
    writer.close()
}