我们来看看给定矩阵的每一行是否完全由 $1$ 构成。
创建一个新数组 $canWin$，如果第 $i$ 行至少包含一个 $0$，则设置 $canWin_i$ 等于 $1$。

那么问题就转化为：在 $canWin$ 数组中寻找只包含 $1$ 的最长子段。
这可以通过对 $canWin$ 的每个元素，找到其左侧最近的 $0$ 的位置来解决。这种解法的复杂度为 $O(nd)$。

但由于题目限制允许 $O(nd^2)$ 的解法，你也可以枚举所有可能的子段，并逐一检查每个子段是否全部为 $1$。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

vector<int> g[N];
int color[N]; // 0: uncolored, 1: color A, 2: color B
int n, m;

bool bfs(int s) {
    queue<int> q;
    q.push(s);
    color[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (color[v] == 0) {
                color[v] = 3 - color[u]; // 1->2, 2->1
                q.push(v);
            } else if (color[v] == color[u]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 二分图染色
    memset(color, 0, sizeof(color));
    bool ok = true;
    for (int i = 1; i <= n; ++i) {
        if (color[i] == 0 && !g[i].empty()) {
            if (!bfs(i)) {
                ok = false;
                break;
            }
        }
    }

    if (!ok) {
        cout << -1 << '\n';
        return 0;
    }

    vector<int> A, B;
    for (int i = 1; i <= n; ++i) {
        if (color[i] == 1) A.push_back(i);
        else if (color[i] == 2) B.push_back(i);
        // 颜色0的孤立点不输出
    }

    // 由于 m >= 1，至少有一条边，A 和 B 均非空
    cout << A.size() << '\n';
    for (size_t i = 0; i < A.size(); ++i) {
        cout << A[i] << " \n"[i == A.size() - 1];
    }
    cout << B.size() << '\n';
    for (size_t i = 0; i < B.size(); ++i) {
        cout << B[i] << " \n"[i == B.size() - 1];
    }

    return 0;
}