tears.cpp

#include <ametus.h>

MI cin;

const int $n = 600005;

int n, m, f[$n], s[$n], e[$n][2];
std::set<std::pair<int, int>> w[$n];
inline int getf(int x) { return f[x] == x? x: (f[x] = getf(f[x])); }
inline void merge(int x, int y) {
    static int q[$n][2], hd, tl;
    hd = 1, tl = 0; q[++tl][0] = x; q[tl][1] = y;
    while (hd <= tl) {
        x = getf(q[hd][0]); y = getf(q[hd++][1]); if (x == y) continue;
        if (w[x].size() > w[y].size()) std::swap(x, y);
        f[x] = y; s[y] += s[x]; s[x] = 0;
        for (auto [t, d] : w[x])
            if (getf(t) == y) q[++tl][0] = e[d][0], q[tl][1] = e[d][1];
            else w[y].emplace(t, d);
    }
}
int main() {
    cin > n > m;
    E(i, n) f[i] = i, s[i] = 1;
    int tp = 0;
    E(m) {
        let op = R;
        switch (op) {
            case 1: {
                let a = getf(R), b = getf(R), c = R, d = R;
                if (a == b) merge(c, d);
                else {
                    e[++tp][0] = c; e[tp][1] = d;
                    w[a].emplace(b, tp);
                    w[b].emplace(a, tp);
                }
                break;
            }
            case 2: merge(R, R); break;
            case 3: cout < ((getf(R) == getf(R))? "entangled\n": "separate\n"); break;
            case 4: cout < s[getf(R)] < endl; break;
            default: assert(0);
        }
    }
}