昨天的 C 蒟蒻 FST 了，一直 WA on Test 29, 请问那里写挂了？

思路是对于每一个颜色的内部都看一下可不可行。然后再对于两种颜色内部用可撤销并查集判以下可不可行。

这个可撤销并查集已经是从网上抄的了，应该没有问题。

#include<bits/stdc++.h>
using namespace std;
#define L(i, j, k) for(int i = (j), i##E = (k); i <= i##E; i++) 
#define R(i, j, k) for(int i = (j), i##E = (k); i >= i##E; i--) 
#define ll long long 
#define db double
#define mkp make_pair 
const int N = 1e6 + 7;
int fa[N], pp[N];
int cntmerge;
stack< pair<int*,int> > sta;
int find(int p) {
    return fa[p] == p ? p : find(fa[p]);
}
void merge(int p,int q) {
    p = find(p), q = find(q);
    if(p != q) {
        ++cntmerge;
        if(pp[p] > pp[q]) swap(p, q);
        sta.push({fa+p,fa[p]});
        fa[p] = q;
        if(pp[p] == pp[q]) sta.push({pp + q, pp[q]}), ++pp[q];
        else sta.push({NULL,0});
    }
}
void _undo() {
    if(sta.size() == 0) return;
    if(sta.top().first != NULL) *sta.top().first=sta.top().second;
    sta.pop();
}
void ud() { _undo(), _undo(); }
int flag[N];
struct node { int fr, to; } e[N];
int n, m, k, a[N], tot;
struct todo { int u, v, bh; } ask[N];
ll ans = 0;
bool cmp(todo aa, todo bb) { return aa.u == bb.u ? aa.u < bb.u : aa.v < bb.v; }
int main() {
    scanf("%d%d%d", &n, &m, &k);
    L(i, 1, 2 * n) fa[i] = i, pp[i] = 1;
    L(i, 1, n) scanf("%d", &a[i]);
    L(i, 1, m) {
        scanf("%d%d", &e[i].fr, &e[i].to);
        if(a[e[i].fr] == a[e[i].to]) merge(e[i].fr, e[i].to + n), merge(e[i].fr + n, e[i].to);
        else ++tot, ask[tot].u = a[e[i].fr], ask[tot].v = a[e[i].to], ask[tot].bh = i;
    } 
    L(i, 1, tot) if(ask[i].u > ask[i].v) swap(ask[i].u, ask[i].v);
    int cnt = 0;
    L(i, 1, n) if(find(i) == find(i + n)) flag[a[i]] = 1;
    L(i, 1, k) if(!flag[i]) cnt++;
    ans = 1ll * cnt * (cnt - 1) / 2;
    sort(ask + 1, ask + tot + 1, cmp);
    int las = 1;
    L(i, 1, tot) {
        if(ask[i].u != ask[i + 1].u || ask[i].v != ask[i + 1].v) {
            int u = ask[i].u, v = ask[i].v;
            if(!flag[u] && !flag[v]) {
                cntmerge = 0;
                L(j, las, i) {
                    int fu = e[ask[j].bh].fr, fv = e[ask[j].bh].to;
                    if(find(fu) == find(fv)) {
                        ans--;
                        break;
                    }
                    merge(fu, fv + n), merge(fu + n, fv);
                }
                while(cntmerge--) ud();
            }
            las = i + 1;
        } 
    }
    if(las != tot + 1) assert(0);
    printf("%lld\n", ans);
    return 0;
}