思路和题解完全一致

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10, M = N;
int n, m;
int e[M], nxt[M], idx = 1, h[N];
void add(int a, int b) {
    e[idx] = b, nxt[idx] = h[a], h[a] = idx++;
}
stack<int> s;
bool st[N];
int low[N], dfn[N], id[N], stmp, scc;
void tarjan(int u) {
    low[u] = dfn[u] = ++stmp;
    s.push(u), st[u] = true;
    for (int i = h[u]; i; i = nxt[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (st[j])
            low[u] = min(low[u], dfn[j]);
    }

    if (low[u] == dfn[u]) {
        int y;
        ++scc;
        do {
            y = s.top();
            s.pop(), st[y] = false;
            id[y] = scc;
        } while (y != u);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
#else
    cin.tie(0)->sync_with_stdio(0);
#endif
    cin >> n >> m;
    while (m--) {
        int i, a, j, b;
        cin >> i >> a >> j >> b;
        add(i + n * (a & 1), j + n * (b ^ 1));
        add(j + n * (b & 1), i + n * (a ^ 1));
    }
    for (int i = 1; i <= n * 2; ++i)
        if (!dfn[i])
            tarjan(i);

    for (int i = 1; i <= n; ++i)
        if (id[i] == id[i + n])
            return cout << "IMPOSSIBLE", 0;
    cout << "POSSIBLE\n";
    for (int i = 1; i <= n; ++i) {
        cout << (id[i + n] > id[n]) << " ";
    }
}