CF 1578 K

#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#define pb emplace_back

using namespace std;

template <size_t maxn>
struct MaximumIndependentSet {
    using BS = bitset<maxn>;
    BS g[maxn];
    int ans;
    BS ans_mask;
    void addEdge(int a, int b) {
        g[a][b] = g[b][a] = true;
    }
    BS solve(int n) {
        ans = n;
        BS select, alive;
        for(int i = 0; i < n; i++) alive[i] = true;
        dfs(0, select, alive);
        return ~ans_mask;
    }
    void dfs(int c, BS select, BS alive) {
        if (c > ans) return;
        // reduce
        int mx = -1, mxDeg = -1;
        for (size_t i = alive._Find_first(); i < maxn; i = alive._Find_next(i)) {
            int deg = (alive & g[i]).count();
            if(deg == 1) {
                int j = (alive & g[i])._Find_first();
                alive[i] = alive[j] = false;
                select[j] = true;
                dfs(c+1, select, alive);
                return;
            }
            if(deg != 0 && deg > mxDeg)
                mx = i, mxDeg = deg;
        }
        if(mx == -1) {
            if (ans > c)
                ans = c, ans_mask = select;
            return;
        }
        alive[mx] = false;
        select[mx] = true;
        dfs(c+1, select, alive);
        alive[mx] = true;
        select[mx] = false;
        BS adj = alive & g[mx];
        dfs(c + adj.count(), select | adj, alive ^ adj);
    }
};

MaximumIndependentSet<80> qlig;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int C, n;
    cin >> C >> n;
    vector<int> s(n);
    for (int i = 0; i < n; i++)
        cin >> s[i], --s[i];
    vector<vector<int>> this_color(C);
    vector<bool> color_changed(C);
    vector<bool> vertex_changed(n);
    for (int i = 0; i < n; i++) {
        this_color[s[i]].emplace_back(i);
    }

    vector<int> vtx;
    int k;
    cin >> k;
    vector<pair<int,int>> E;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        color_changed[s[a]] = true;
        color_changed[s[b]] = true;
        vertex_changed[a] = true;
        vertex_changed[b] = true;
        vtx.emplace_back(a);
        vtx.emplace_back(b);
        E.emplace_back(a, b);
        E.emplace_back(b, a);
    }
    sort(E.begin(), E.end());


    vector<int> ans;
    for (int i = 0; i < C; i++) {
        if (color_changed[i]) {
            int x = -1;
            for (int y: this_color[i])
                if (!vertex_changed[y]) {
                    x = y;
                    break;
                }
            if (x != -1)
                vtx.emplace_back(x);
        } else {
            if (this_color[i].size() > 0) {
                ans.emplace_back(this_color[i][0]);
            }
        }
    }

    sort(vtx.begin(), vtx.end());
    vtx.erase(unique(vtx.begin(), vtx.end()), vtx.end());

    int V = vtx.size();

    assert(V <= 80);
    // qlig.init(V);
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < i; j++) {
            int x = vtx[i], y = vtx[j];
            bool hasEdge =
                binary_search(E.begin(), E.end(),
                        make_pair(x, y));
            if ((s[x] == s[y]) ^ hasEdge) {
                // cerr << "addedge " << x << ',' << y << endl;
                qlig.addEdge(i, j);
            }
        }
    }

    auto msk = qlig.solve(V);
    // cerr << msk << endl;
    for (int i = 0; i < V; i++) {
        if (msk[i]) {
            ans.emplace_back(vtx[i]);
        }
    }

    cout << ans.size() << '\n';
    for (int i = 0; i < (int)ans.size(); i++) {
        cout << ans[i]+1 << " \n"[i+1 == (int)ans.size()];
    }
}