记录编号	610251	评测结果	AAAAAAAAAAAAAA
题目名称	[POI 2001] 和平委员会	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.534 s
提交时间	2025-12-18 22:44:15	内存使用	4.25 MiB

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

const int MAXN = 16005;
int n, m;
vector<int> g[MAXN];
bool vis[MAXN];
int S[MAXN], c = 0;

inline int get_id(int x) {
    x--;
    return x;
}

bool dfs(int u) {
    if (vis[u ^ 1]) return false;
    if (vis[u]) return true;
    vis[u] = true;
    S[c++] = u;
    for (int v : g[u]) {
        if (!dfs(v)) return false;
    }
    return true;
}

bool Two_SAT() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 2 * n; i += 2) {
        if (!vis[i] && !vis[i + 1]) {
            c = 0;
            if (!dfs(i)) {
                while (c > 0) vis[S[--c]] = false;
                if (!dfs(i + 1)) {
                    return false;
                }
            }
        }
    }
    return true;
}

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

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        int u = get_id(a);
        int v = get_id(b);
        g[u].push_back(v ^ 1);
        g[v].push_back(u ^ 1);
    }

    if (!Two_SAT()) {
        cout << "NIE" << endl;
    } else {
        vector<int> ans;
        for (int i = 0; i < 2 * n; i += 2) {
            if (vis[i]) {
                ans.push_back(i + 1);
            } else {
                ans.push_back(i + 2);
            }
        }
        sort(ans.begin(), ans.end());
        for (int x : ans) {
            cout << x << endl;
        }
    }

    return 0;
}