lessons/参考实现/10-高斯消元与CRT/AtCoder-abc366_g.cpp

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

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

    int n, m;
    cin >> n >> m;
    vector<unsigned long long> row(n, 0);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        row[u] ^= 1ULL << v;
        row[v] ^= 1ULL << u;
    }

    vector<int> pivot_column;
    int rank = 0;
    for (int column = 0; column < n; ++column) {
        int pivot = rank;
        while (pivot < n && ((row[pivot] >> column) & 1ULL) == 0) ++pivot;
        if (pivot == n) continue;
        swap(row[rank], row[pivot]);
        for (int r = 0; r < n; ++r) {
            if (r != rank && ((row[r] >> column) & 1ULL)) row[r] ^= row[rank];
        }
        pivot_column.push_back(column);
        ++rank;
    }

    vector<char> is_pivot(n, false);
    for (int column : pivot_column) is_pivot[column] = true;
    vector<unsigned long long> answer(n, 0);
    int basis_index = 0;
    for (int free_column = 0; free_column < n; ++free_column) {
        if (is_pivot[free_column]) continue;
        unsigned long long vector_value = 1ULL << free_column;
        for (int r = 0; r < rank; ++r) {
            if ((row[r] >> free_column) & 1ULL) {
                vector_value |= 1ULL << pivot_column[r];
            }
        }
        for (int v = 0; v < n; ++v) {
            if ((vector_value >> v) & 1ULL) answer[v] |= 1ULL << basis_index;
        }
        ++basis_index;
    }
    if (find(answer.begin(), answer.end(), 0ULL) != answer.end()) {
        cout << "No\n";
        return 0;
    }
    cout << "Yes\n";
    for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << answer[i];
    }
    cout << '\n';
    return 0;
}