Bài này mình dùng dfs để giải:

* Nếu người v chưa có nhóm (chắc chắn là không quen (v - 1) người trước đó) thì cho vào nhóm 1

* Nếu người u quen người v:

- u đã có nhóm: 

 + nhóm của u = nhóm của v : không chia được

- u chưa có nhóm:

 + cho u vào nhóm còn lại

** g ^ 3 có tác dụng để đổi nhóm sẽ cho {v} vào:

nếu g = 1 -> g ^ 3 = 2

nếu g = 2 -> g ^ 3 = 1

- Code

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e3 + 2;
bool checkans = 1;
vector<int> o;
int a[N][N];
int n;

void dfs(int v, int p, int g) {
    if (o[v] == o[p]) {
        checkans = 0;
        return;
    }
    
    if (o[v] != 0) return;
    o[v] = g;
    
    for (int i = 1; i <= n; ++i) {
        if (a[i][v] == 1 && i != p) dfs(i, v, g ^ 3);
    }

}

int main() {
    cin >> n;
    o = vector<int>(n + 5);
    o[0] = -1;
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= n; ++j) cin >> a[i][j];
    
    for (int i = 1; i <= n; ++i) {
        if (o[i] == 0) dfs(i, 0, 1);
    }

    if (checkans == 0) cout << -1; else {
        for (int i = 1; i <= n; ++i) if (o[i] == 1) cout << i << " "; cout << "\n";
        for (int i = 1; i <= n; ++i) if (o[i] == 2) cout << i << " "; cout << "\n";
    }
    // Ổn không nhỉ :))
}