ต้นไม้บนแกนเวลา: เปลี่ยน "เพิ่มแล้วลบ" ให้เหลือแค่ "เพิ่มแล้วย้อนกลับ"

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

const int MAXN = 300005, MAXQ = 300005;   // จุดเวลา = คำถาม ? ซึ่งมีไม่เกิน K
int n, K, Q, comps;
int par[MAXN], sz[MAXN];
vector<int> stk;                  // ลูกที่ถูกย้ายไปขึ้นกับแม่ เรียงตามลำดับที่รวม
vector<pair<int,int>> node[4 * MAXQ];
int ans[MAXQ];

// ไม่บีบทางเดิน เพราะการบีบแก้ par หลายช่องที่สแต็กไม่ได้จดไว้ ย้อนกลับไม่ได้
int find(int x) {
    while (par[x] != x) x = par[x];
    return x;
}

bool unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
    stk.push_back(b);
    comps--;
    return true;
}

void rollback(int keep) {
    while ((int)stk.size() > keep) {
        int b = stk.back(); stk.pop_back();
        sz[par[b]] -= sz[b];
        par[b] = b;
        comps++;
    }
}

void addRange(int v, int l, int r, int ql, int qr, pair<int,int> item) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { node[v].push_back(item); return; }
    int mid = (l + r) / 2;
    addRange(2 * v, l, mid, ql, qr, item);
    addRange(2 * v + 1, mid + 1, r, ql, qr, item);
}

void dfs(int v, int l, int r) {
    int keep = stk.size();
    for (auto [a, b] : node[v]) unite(a, b);
    if (l == r) ans[l] = comps;
    else {
        int mid = (l + r) / 2;
        dfs(2 * v, l, mid);
        dfs(2 * v + 1, mid + 1, r);
    }
    rollback(keep);
}

int main() {
    freopen("connect.in", "r", stdin);
    freopen("connect.out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> K;
    // แกนเวลานับเฉพาะคำถาม ? เพราะเป็นจุดเดียวที่ต้องรู้คำตอบ
    // เส้นที่เกิดตอนถามไปแล้ว c ข้อ จะเห็นได้ตั้งแต่คำถามที่ c
    vector<tuple<int,int,pair<int,int>>> lives;   // (คำถามแรก, คำถามสุดท้าย, เส้น)
    map<pair<int,int>, int> born;                 // เส้นที่ยังอยู่ -> คำถามแรกที่เห็นมัน
    Q = 0;
    for (int i = 0; i < K; i++) {
        char c; cin >> c;
        if (c == '?') { Q++; continue; }
        int u, v; cin >> u >> v;
        pair<int,int> e = {min(u, v), max(u, v)};   // ไม่มีทิศ: "- 2 1" คือเส้นเดียวกับ "+ 1 2"
        if (c == '+') born[e] = Q;
        else {
            lives.push_back({born[e], Q - 1, e});    // ช่วงว่างได้ ถ้าไม่มีคำถามคั่นระหว่างเกิดกับตาย
            born.erase(e);
        }
    }
    if (Q == 0) return 0;
    for (auto [e, s] : born) lives.push_back({s, Q - 1, e});
    for (auto [l, r, e] : lives) if (l <= r) addRange(1, 0, Q - 1, l, r, e);

    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    comps = n;
    dfs(1, 0, Q - 1);
    for (int i = 0; i < Q; i++) cout << ans[i] << '\n';
    return 0;
}

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

const int MAXN = 100005, MAXQ = 100005;
int n, q;
int par[MAXN], sz[MAXN], d[MAXN];   // d[x] = x กับ par[x] ต่างสีกันไหม (0 สีเดียวกัน, 1 ต่างสี)
vector<int> stk;                     // ลูกที่ถูกย้ายไปขึ้นกับแม่ เรียงตามลำดับที่รวม
vector<pair<int,int>> node[4 * MAXQ];
bool ans[MAXQ];                      // ใบที่ DFS ไปไม่ถึงคือใบที่มีวงคี่แล้ว ค่าเริ่มต้น false จึงถูกอยู่แล้ว

// ไม่บีบทางเดิน คืนราก และสีของ x เทียบกับราก (xor ของ d ตลอดทาง)
pair<int,int> find(int x) {
    int c = 0;
    while (par[x] != x) c ^= d[x], x = par[x];
    return {x, c};
}

// คืน false เมื่อเส้น a-b ปิดวงคี่ (a กับ b อยู่ก๊วนเดียวกันและสีเดียวกันอยู่แล้ว)
bool unite(int a, int b) {
    auto [ra, ca] = find(a);
    auto [rb, cb] = find(b);
    if (ra == rb) return ca != cb;
    if (sz[ra] < sz[rb]) swap(ra, rb);
    par[rb] = ra;
    d[rb] = ca ^ cb ^ 1;   // ให้ a กับ b ต่างสีกัน: ca ^ (d[rb] ^ cb) = 1
    sz[ra] += sz[rb];
    stk.push_back(rb);
    return true;
}

void rollback(int keep) {
    while ((int)stk.size() > keep) {
        int b = stk.back(); stk.pop_back();
        sz[par[b]] -= sz[b];
        par[b] = b;   // d[b] ไม่ต้องคืน: รากไม่มีใครอ่าน d และจะถูกเขียนทับเมื่อ b ถูกรวมอีกครั้ง
    }
}

void addRange(int v, int l, int r, int ql, int qr, pair<int,int> item) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { node[v].push_back(item); return; }
    int mid = (l + r) / 2;
    addRange(2 * v, l, mid, ql, qr, item);
    addRange(2 * v + 1, mid + 1, r, ql, qr, item);
}

void dfs(int v, int l, int r) {
    int keep = stk.size();
    bool odd = false;
    for (auto [a, b] : node[v]) if (!unite(a, b)) { odd = true; break; }
    // เส้นบนปมนี้อยู่ครบทุกใบข้างใต้ วงคี่จึงอยู่ในทุกใบ ไม่ต้องลงไปต่อ
    if (!odd) {
        if (l == r) ans[l] = true;
        else {
            int mid = (l + r) / 2;
            dfs(2 * v, l, mid);
            dfs(2 * v + 1, mid + 1, r);
        }
    }
    rollback(keep);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q;
    map<pair<int,int>, int> born;    // เส้นที่ยังอยู่ -> คำถามแรกที่มีมัน
    for (int i = 0; i < q; i++) {
        int x, y; cin >> x >> y;     // โจทย์รับประกัน x < y จึงใช้เป็นกุญแจได้ตรง ๆ
        auto it = born.find({x, y});
        if (it == born.end()) born[{x, y}] = i;
        else {
            addRange(1, 0, q - 1, it->second, i - 1, it->first);   // ถูกลบที่คำถาม i
            born.erase(it);
        }
    }
    for (auto [e, s] : born) addRange(1, 0, q - 1, s, q - 1, e);

    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    dfs(1, 0, q - 1);
    for (int i = 0; i < q; i++) cout << (ans[i] ? "YES" : "NO") << '\n';
    return 0;
}

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

// ปม 1..C คือ "แถว x" ปม C+1..2C คือ "หลัก y" จุด (x, y) คือเส้นเชื่อมแถว x กับหลัก y
const int C = 300000;
vector<int> par, sz, cx, cy;   // cx, cy = จำนวนแถว / หลักในก๊วนที่ปมนี้เป็นหัว
vector<int> stk;               // ลูกที่ถูกย้ายไปขึ้นกับแม่ เรียงตามลำดับที่รวม
ll ans;                        // ผลรวม cx*cy ของทุกก๊วน = ขนาดของ E(S)

int find(int x) {              // ไม่บีบทางเดิน เพราะต้อง rollback ได้
    while (par[x] != x) x = par[x];
    return x;
}

void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    ans -= (ll)cx[a] * cy[a] + (ll)cx[b] * cy[b];
    par[b] = a, sz[a] += sz[b], cx[a] += cx[b], cy[a] += cy[b];
    ans += (ll)cx[a] * cy[a];
    stk.push_back(b);
}

void rollback(int keep) {
    while ((int)stk.size() > keep) {
        int b = stk.back(), a = par[b];
        stk.pop_back();
        // แยกก๊วนกลับเป็นสองก้อน แล้วคิดผลคูณของทั้งสองก้อนใหม่
        ans -= (ll)cx[a] * cy[a];
        sz[a] -= sz[b], cx[a] -= cx[b], cy[a] -= cy[b];
        par[b] = b;
        ans += (ll)cx[a] * cy[a] + (ll)cx[b] * cy[b];
    }
}

int Q;
vector<vector<pair<int,int>>> node;   // node[v] = จุดที่มีชีวิตตลอดช่วงของปม v

void addRange(int v, int l, int r, int ql, int qr, pair<int,int> item) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { node[v].push_back(item); return; }
    int m = (l + r) / 2;
    addRange(2 * v, l, m, ql, qr, item);
    addRange(2 * v + 1, m + 1, r, ql, qr, item);
}

vector<ll> res;

void dfs(int v, int l, int r) {
    int keep = stk.size();
    for (auto [x, y] : node[v]) unite(x, C + y);
    if (l == r) res[l] = ans;
    else {
        int m = (l + r) / 2;
        dfs(2 * v, l, m);
        dfs(2 * v + 1, m + 1, r);
    }
    rollback(keep);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> Q;
    par.resize(2 * C + 1), sz.assign(2 * C + 1, 1);
    cx.assign(2 * C + 1, 0), cy.assign(2 * C + 1, 0);
    for (int i = 1; i <= 2 * C; i++) par[i] = i;
    for (int i = 1; i <= C; i++) cx[i] = 1, cy[C + i] = 1;
    stk.clear(), ans = 0;
    node.assign(4 * Q, {}), res.assign(Q, 0);

    map<pair<int,int>, int> since;   // จุดที่อยู่ใน S ตอนนี้ -> คำถามที่มันถูกเติมเข้ามา
    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        auto it = since.find({x, y});
        if (it == since.end()) since[{x, y}] = i;
        else {
            addRange(1, 0, Q - 1, it->second, i - 1, {x, y});
            since.erase(it);
        }
    }
    for (auto [p, t] : since) addRange(1, 0, Q - 1, t, Q - 1, p);

    dfs(1, 0, Q - 1);
    for (int i = 0; i < Q; i++) cout << res[i] << (i + 1 < Q ? ' ' : '\n');
    return 0;
}

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

vector<int> par, sz;
vector<int> stk;   // ลูกที่ถูกย้ายไปขึ้นกับแม่ เรียงตามลำดับที่รวม

int find(int x) {  // ไม่บีบทางเดิน เพราะต้อง rollback ได้
    while (par[x] != x) x = par[x];
    return x;
}

void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a, sz[a] += sz[b];
    stk.push_back(b);
}

void rollback(int keep) {
    while ((int)stk.size() > keep) {
        int b = stk.back();
        stk.pop_back();
        sz[par[b]] -= sz[b];
        par[b] = b;
    }
}

int Q;
vector<vector<pair<int,int>>> node;   // node[v] = การพบกันที่ยังนับอยู่ตลอดช่วงของปม v

void addRange(int v, int l, int r, int ql, int qr, pair<int,int> item) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { node[v].push_back(item); return; }
    int m = (l + r) / 2;
    addRange(2 * v, l, m, ql, qr, item);
    addRange(2 * v + 1, m + 1, r, ql, qr, item);
}

vector<int> type, who, res;

void dfs(int v, int l, int r) {
    int keep = stk.size();
    for (auto [x, y] : node[v]) unite(x, y);
    if (l == r) {
        if (type[l] == 2) res[l] = sz[find(who[l])];
    } else {
        int m = (l + r) / 2;
        dfs(2 * v, l, m);
        dfs(2 * v + 1, m + 1, r);
    }
    rollback(keep);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> Q >> k;
    par.resize(n + 1), sz.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) par[i] = i;
    stk.clear();
    node.assign(4 * Q, {});
    type.assign(Q, 0), who.assign(Q, 0), res.assign(Q, 0);

    // dayStart[d] = คำถามแรกของวันที่ d (วันแรกคือวันที่ 0 และขึ้นวันใหม่หลังคำสั่งแบบ 3)
    vector<int> dayStart = {0};
    vector<array<int,4>> meet;   // x, y, คำถามที่พบ, วันที่พบ
    for (int i = 0; i < Q; i++) {
        cin >> type[i];
        if (type[i] == 1) {
            int x, y;
            cin >> x >> y;
            meet.push_back({x, y, i, (int)dayStart.size() - 1});
        } else if (type[i] == 2) {
            cin >> who[i];
        } else {
            dayStart.push_back(i + 1);
        }
    }
    // พบกันวันที่ d ยังนับอยู่ถึงวันที่ d+k-1 จึงหมดอายุตอนเริ่มวันที่ d+k
    for (auto [x, y, i, d] : meet) {
        int end = d + k < (int)dayStart.size() ? dayStart[d + k] - 1 : Q - 1;
        addRange(1, 0, Q - 1, i, end, {x, y});
    }

    dfs(1, 0, Q - 1);
    for (int i = 0; i < Q; i++)
        if (type[i] == 2) cout << res[i] << '\n';
    return 0;
}

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

const int N = 10005;  // n สูงสุด 10^4 บวกช่องสำหรับค่า 0
const int LOG = 16;   // ต้นไม้ช่วงบน 10^4 ตำแหน่งลึกไม่เกิน 14 ชั้น

int n, q;
vector<int> node[4 * N];     // คำสั่งที่ครอบช่วงของปมนี้ทั้งช่วง เก็บแค่ค่า x
bitset<N> reach[LOG];        // reach[dep] = ผลรวมที่ทำได้ ณ ความลึก dep (บิต s เปิด = ทำผลรวม s ได้)
bitset<N> ans;

// แกนของต้นไม้คือ "ตำแหน่ง" ในอาร์เรย์ ไม่ใช่เวลา
void addRange(int v, int l, int r, int ql, int qr, int item) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { node[v].push_back(item); return; }
    int m = (l + r) / 2;
    addRange(2 * v, l, m, ql, qr, item);
    addRange(2 * v + 1, m + 1, r, ql, qr, item);
}

// reach[dep] ถูกเตรียมจากแม่ไว้แล้ว ปมนี้เติมของตัวเองลงไป แล้วส่งสำเนาต่อให้ลูก
// ไม่ต้องลบอะไรเลย เพราะสำเนาของแม่ที่ reach[dep-1] ยังอยู่ครบ
void dfs(int v, int l, int r, int dep) {
    for (int x : node[v]) reach[dep] |= reach[dep] << x;  // บิตที่เลื่อนเกิน n หลุดทิ้งเอง
    if (l == r) { ans |= reach[dep]; return; }
    int m = (l + r) / 2;
    reach[dep + 1] = reach[dep];
    dfs(2 * v, l, m, dep + 1);
    reach[dep + 1] = reach[dep];
    dfs(2 * v + 1, m + 1, r, dep + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 0; i < q; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        addRange(1, 1, n, l, r, x);
    }
    reach[0][0] = 1;  // ไม่เลือกคำสั่งใดเลย ผลรวมเป็น 0
    dfs(1, 1, n, 0);
    // ถ้าตำแหน่ง p ทำผลรวม y ได้ด้วยคำสั่งชุดที่คลุม p ทุกตัว ตำแหน่งอื่นได้แค่บางตัวในชุดนั้น
    // จึงไม่เกิน y ค่าสูงสุดของอาร์เรย์เลยเท่ากับ y พอดี
    vector<int> out;
    for (int y = 1; y <= n; y++)
        if (ans[y]) out.push_back(y);
    cout << out.size() << "\n";
    for (int y : out) cout << y << " ";
    cout << "\n";
}

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

const int Q = 30005;        // จำนวนเหตุการณ์ประเภท 3 มากสุด 30000
const int K = 1005;         // มวลที่สนใจมากสุด 1000
const int LOG = 17;         // ต้นไม้ช่วงบน 30000 ใบลึกไม่เกิน 15 ชั้น
const ll P = 10000019, MOD = 1000000007;

int k;
vector<pair<int, int>> node[4 * Q];  // ของ (ราคา, มวล) ที่อยู่ในตู้ตลอดช่วงของปมนี้
ll dp[LOG][K];              // dp[dep][m] = ราคารวมสูงสุดเมื่อมวลรวมไม่เกิน m ณ ความลึก dep
ll ans[Q];

void addRange(int v, int l, int r, int ql, int qr, pair<int, int> item) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { node[v].push_back(item); return; }
    int m = (l + r) / 2;
    addRange(2 * v, l, m, ql, qr, item);
    addRange(2 * v + 1, m + 1, r, ql, qr, item);
}

// knapsack ถอดของออกไม่ได้ จึงไม่ถอด: ลูกทำงานบนสำเนา dp[dep+1]
// พอกลับขึ้นมา dp[dep] ของแม่ยังไม่ถูกแตะ นี่คือ "ย้อนกลับ" ด้วยการเก็บสำเนา
void dfs(int v, int l, int r, int dep) {
    ll* f = dp[dep];
    for (auto [val, w] : node[v])
        for (int m = k; m >= w; m--) f[m] = max(f[m], f[m - w] + val);
    if (l == r) {
        ll h = 0, pw = 1;
        for (int m = 1; m <= k; m++) {
            h = (h + f[m] % MOD * pw) % MOD;
            pw = pw * P % MOD;
        }
        ans[l] = h;
        return;
    }
    int m = (l + r) / 2;
    copy(f, f + k + 1, dp[dep + 1]);
    dfs(2 * v, l, m, dep + 1);
    copy(f, f + k + 1, dp[dep + 1]);
    dfs(2 * v + 1, m + 1, r, dep + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> k;
    // from = คำถามแรกที่เห็นของชิ้นนี้, to = คำถามสุดท้ายที่ยังเห็น
    // ของที่ไม่เคยถูกเก็บเข้าห้องนิรภัยใช้ค่า ALIVE ห้ามใช้ -1 เพราะของที่ถูกเก็บก่อนคำถามแรกได้ to = -1 จริง
    const int ALIVE = INT_MAX;
    vector<int> v(n), w(n), from(n, 0), to(n, ALIVE);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];
    cin >> q;
    int T = 0;  // จำนวนคำถาม (เหตุการณ์ประเภท 3) ใบของต้นไม้คือคำถามลำดับ 0..T-1
    for (int e = 0; e < q; e++) {
        int type;
        cin >> type;
        if (type == 1) {
            int a, b;
            cin >> a >> b;
            v.push_back(a); w.push_back(b);
            from.push_back(T); to.push_back(ALIVE);
        } else if (type == 2) {
            int x;
            cin >> x;
            to[x - 1] = T - 1;
        } else {
            T++;
        }
    }
    for (int i = 0; i < (int)v.size(); i++) {
        int r = to[i] == ALIVE ? T - 1 : to[i];
        if (from[i] <= r) addRange(1, 0, T - 1, from[i], r, {v[i], w[i]});
    }
    dfs(1, 0, T - 1, 0);  // dp[0] เป็นศูนย์ทั้งแถว (ยังไม่มีของ)
    for (int i = 0; i < T; i++) cout << ans[i] << "\n";
}

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

const int Q = 30005;        // จำนวนเหตุการณ์ประเภท 3 มากสุด 30000
const int K = 1005;         // มวลที่สนใจมากสุด 1000
const int LOG = 17;         // ต้นไม้ช่วงบน 30000 ใบลึกไม่เกิน 16 ชั้น
const ll P = 10000019, MOD = 1000000007;

int k, T;                   // T = จำนวนคำถาม (เหตุการณ์ประเภท 3) ใบของต้นไม้คือคำถามลำดับ 0..T-1
vector<pair<int, int>> node[4 * Q];  // ของ (ราคา, มวล) ที่อยู่ในตู้ตลอดช่วงของปมนี้
ll dp[LOG][K];              // dp[dep][m] = ราคารวมสูงสุดเมื่อมวลรวมไม่เกิน m ณ ความลึก dep
ll ans[Q];

void addRange(int v, int l, int r, int ql, int qr, pair<int, int> item) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { node[v].push_back(item); return; }
    int m = (l + r) / 2;
    addRange(2 * v, l, m, ql, qr, item);
    addRange(2 * v + 1, m + 1, r, ql, qr, item);
}

// knapsack ถอดของออกไม่ได้ จึงไม่ถอด: ลูกทำงานบนสำเนา dp[dep+1]
// พอกลับขึ้นมา dp[dep] ของแม่ยังไม่ถูกแตะ นี่คือ "ย้อนกลับ" ด้วยการเก็บสำเนา
void dfs(int v, int l, int r, int dep) {
    ll* f = dp[dep];
    for (auto [val, w] : node[v])
        for (int m = k; m >= w; m--) f[m] = max(f[m], f[m - w] + val);
    if (l == r) {
        ll h = 0, pw = 1;
        for (int m = 1; m <= k; m++) {
            h = (h + f[m] % MOD * pw) % MOD;
            pw = pw * P % MOD;
        }
        ans[l] = h;
        return;
    }
    int m = (l + r) / 2;
    copy(f, f + k + 1, dp[dep + 1]);
    dfs(2 * v, l, m, dep + 1);
    copy(f, f + k + 1, dp[dep + 1]);
    dfs(2 * v + 1, m + 1, r, dep + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> k;
    // ของแต่ละชิ้น: ราคา, มวล, คำถามแรกที่เห็นมัน (นับจำนวนคำถามก่อนหน้าตอนที่ของเข้าตู้)
    vector<int> v(n), w(n), from(n, 0), to(n, -1);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];
    cin >> q;
    T = 0;
    for (int e = 0; e < q; e++) {
        int type;
        cin >> type;
        if (type == 1) {
            int a, b;
            cin >> a >> b;
            v.push_back(a); w.push_back(b);
            from.push_back(T); to.push_back(-1);
        } else if (type == 2) {
            int x;
            cin >> x;
            to[x - 1] = T - 1;  // คำถามสุดท้ายที่ยังเห็นของชิ้นนี้
        } else {
            T++;
        }
    }
    for (int i = 0; i < (int)v.size(); i++) {
        int r = to[i] == -1 ? T - 1 : to[i];
        if (from[i] <= r) addRange(1, 0, T - 1, from[i], r, {v[i], w[i]});
    }
    dfs(1, 0, T - 1, 0);  // dp[0] เป็นศูนย์ทั้งแถว (ยังไม่มีของ)
    for (int i = 0; i < T; i++) cout << ans[i] << "\n";
}

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

vector<int> par, sz;
vector<int> stk;   // ลูกที่ถูกย้ายไปขึ้นกับแม่ เรียงตามลำดับที่รวม

int find(int x) {  // ไม่บีบทางเดิน เพราะต้อง rollback ได้
    while (par[x] != x) x = par[x];
    return x;
}

bool unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a, sz[a] += sz[b];
    stk.push_back(b);
    return true;
}

void rollback(int keep) {
    while ((int)stk.size() > keep) {
        int b = stk.back();
        stk.pop_back();
        sz[par[b]] -= sz[b];
        par[b] = b;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> U(m + 1), V(m + 1), W(m + 1);
    for (int i = 1; i <= m; i++) cin >> U[i] >> V[i] >> W[i];
    par.resize(n + 1), sz.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) par[i] = i;
    stk.clear();

    int q;
    cin >> q;
    // แตกแต่ละคำถามเป็นกลุ่มย่อยตามน้ำหนัก: (น้ำหนัก, คำถาม, เส้นในกลุ่ม)
    vector<tuple<int,int,vector<int>>> groups;
    for (int j = 0; j < q; j++) {
        int k;
        cin >> k;
        vector<int> e(k);
        for (int& x : e) cin >> x;
        sort(e.begin(), e.end(), [&](int a, int b) { return W[a] < W[b]; });
        for (int s = 0, t; s < k; s = t) {
            for (t = s; t < k && W[e[t]] == W[e[s]]; t++) {}
            groups.emplace_back(W[e[s]], j, vector<int>(e.begin() + s, e.begin() + t));
        }
    }
    sort(groups.begin(), groups.end(),
         [](const auto& a, const auto& b) { return get<0>(a) < get<0>(b); });

    vector<int> order(m);
    iota(order.begin(), order.end(), 1);
    sort(order.begin(), order.end(), [&](int a, int b) { return W[a] < W[b]; });

    vector<bool> ok(q, true);
    int p = 0;   // เส้นใน order[0..p) ถูกรวมถาวรแล้ว (Kruskal ที่เดินไปถึงก่อนน้ำหนักปัจจุบัน)
    for (auto& [w, j, e] : groups) {
        // เส้นที่เบากว่า w ทุกเส้นต้องรวมแล้ว ส่วนเส้นน้ำหนัก w เองยังห้ามรวม
        while (p < m && W[order[p]] < w) unite(U[order[p]], V[order[p]]), p++;
        if (!ok[j]) continue;
        int keep = stk.size();
        for (int x : e)
            if (!unite(U[x], V[x])) { ok[j] = false; break; }
        rollback(keep);   // ของที่ลองรวมเป็นของคำถามนี้คนเดียว คำถามอื่นต้องไม่เห็น
    }
    for (int j = 0; j < q; j++) cout << (ok[j] ? "YES" : "NO") << '\n';
    return 0;
}

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

int n, m, q;
vector<vector<char>> a;       // a[i][j] ก่อนกลับด้าน: มีหนังสือจริงเมื่อ a[i][j] != inv[i]
vector<int> inv, cnt;         // inv[i] = ชั้น i ถูกกลับด้านอยู่ไหม, cnt[i] = จำนวนหนังสือบนชั้น i
int total;
vector<int> t, x, y, res;
vector<vector<int>> child;    // child[v] = คำสั่งที่ต่อจากเวอร์ชัน v

// กลับด้านชั้น i ทำซ้ำอีกครั้งก็คือการย้อน
void flipShelf(int i) {
    inv[i] ^= 1;
    total += m - 2 * cnt[i];
    cnt[i] = m - cnt[i];
}

// ทำคำสั่ง v คืนว่าตู้เปลี่ยนจริงไหม วางบนช่องที่มีหนังสือหรือหยิบจากช่องว่างไม่เปลี่ยนอะไร
bool apply(int v) {
    if (t[v] == 3) { flipShelf(x[v]); return true; }
    if (t[v] != 1 && t[v] != 2) return false;   // เวอร์ชัน 0 กับคำสั่งแบบ 4 ไม่แตะตู้
    int i = x[v], j = y[v], d = t[v] == 1 ? 1 : -1;
    bool has = a[i][j] != inv[i];
    if (has == (t[v] == 1)) return false;
    a[i][j] ^= 1, cnt[i] += d, total += d;
    return true;
}

// rollback คำสั่ง v ที่เปลี่ยนตู้จริง
void undo(int v) {
    if (t[v] == 3) { flipShelf(x[v]); return; }
    int i = x[v], j = y[v], d = t[v] == 1 ? 1 : -1;
    a[i][j] ^= 1, cnt[i] -= d, total -= d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    a.assign(n + 1, vector<char>(m + 1, 0));
    inv.assign(n + 1, 0), cnt.assign(n + 1, 0), total = 0;
    t.assign(q + 1, 0), x.assign(q + 1, 0), y.assign(q + 1, 0), res.assign(q + 1, 0);
    child.assign(q + 1, {});
    // เวอร์ชัน 0 คือตู้ว่าง คำสั่ง v ต่อจากเวอร์ชัน v-1 ยกเว้นแบบ 4 ที่ต่อจากเวอร์ชัน k
    for (int v = 1; v <= q; v++) {
        cin >> t[v] >> x[v];
        if (t[v] <= 2) cin >> y[v];
        child[t[v] == 4 ? x[v] : v - 1].push_back(v);
    }

    // เดินต้นไม้เวอร์ชันด้วยสแต็กของตัวเอง ต้นไม้ลึกได้ถึง q ชั้น (ถ้าไม่มีแบบ 4 เลย)
    // ถ้าเรียกตัวเองลึกขนาดนั้น สแต็กของโปรแกรมอาจล้น
    vector<char> changed(q + 1, 0);
    vector<pair<int, int>> st = {{0, 0}};   // (เวอร์ชัน, ลูกคนถัดไปที่ต้องลงไป)
    while (!st.empty()) {
        int v = st.back().first;
        int& next = st.back().second;
        if (next < (int)child[v].size()) {
            int c = child[v][next++];
            changed[c] = apply(c);
            res[c] = total;                    // ตู้ในหน่วยความจำตอนนี้คือเวอร์ชัน c พอดี
            st.push_back({c, 0});
        } else {
            if (changed[v]) undo(v);           // ออกจากเวอร์ชัน v ย้อนตู้กลับเป็นเวอร์ชันแม่
            st.pop_back();
        }
    }
    for (int v = 1; v <= q; v++) cout << res[v] << '\n';
    return 0;
}

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

const int N = 200005;
const int Q = 200005;
const int B = 30;          // น้ำหนักมีไม่เกิน 30 บิต
const int LOG = 20;        // ต้นไม้ช่วงบน 2·10^5 ใบลึกไม่เกิน 18 ชั้น

struct Edge { int x, y, w; };

int par[N], sz[N], d[N];   // d[v] = xor ของเส้นจาก v ขึ้นไปถึง par[v]
vector<int> stk;           // ลูกที่ถูกย้ายไปขึ้นกับแม่ ตามลำดับการรวม
vector<Edge> node[4 * Q];
int basis[LOG][B];         // basis[dep][b] = ตัวในฐาน xor ที่บิตสูงสุดคือ b (0 = ว่าง)
int qx[Q], qy[Q];          // คำถามที่เวลา t (qx = 0 ถ้าเวลานั้นไม่ใช่คำถาม)

// ไม่บีบทางเดิน เพื่อให้การรวมหนึ่งครั้งแก้แค่ par, sz, d ของรากเดียว ย้อนกลับได้
// คืนราก และเขียน xor จาก x ถึงรากลงใน dist
int find(int x, int& dist) {
    dist = 0;
    while (par[x] != x) { dist ^= d[x]; x = par[x]; }
    return x;
}

void insertBasis(int* bs, int val) {
    for (int b = B - 1; b >= 0 && val; b--) {
        if (!(val >> b & 1)) continue;
        if (!bs[b]) { bs[b] = val; return; }
        val ^= bs[b];
    }
}

// เส้น x-y น้ำหนัก w: ถ้าอยู่คนละก๊วน ต่อราก ถ้าอยู่ก๊วนเดียวกัน เกิดวงใหม่ ส่ง xor ของวงเข้าฐาน
bool unite(int x, int y, int w, int* bs) {
    int dx, dy;
    int a = find(x, dx), b = find(y, dy);
    if (a == b) { insertBasis(bs, dx ^ dy ^ w); return false; }
    if (sz[a] < sz[b]) swap(a, b);
    // เลือก d[b] ให้ xor จาก x ไป y ผ่านต้นไม้เท่ากับ w พอดี: dx ^ d[b] ^ dy = w
    // สลับ a กับ b แล้วสูตรเดิมยังถูก เพราะ xor สลับที่ได้
    par[b] = a; d[b] = dx ^ dy ^ w; sz[a] += sz[b];
    stk.push_back(b);
    return true;
}

void rollback(int keep) {
    while ((int)stk.size() > keep) {
        int b = stk.back(); stk.pop_back();
        sz[par[b]] -= sz[b];
        par[b] = b;   // d[b] ไม่ต้องคืน: รากไม่มีใครอ่าน d และจะถูกเขียนทับเมื่อ b ถูกรวมอีกครั้ง
    }
}

void addRange(int v, int l, int r, int ql, int qr, Edge item) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { node[v].push_back(item); return; }
    int m = (l + r) / 2;
    addRange(2 * v, l, m, ql, qr, item);
    addRange(2 * v + 1, m + 1, r, ql, qr, item);
}

// DSU ย้อนด้วยสแต็ก ส่วนฐาน xor ย้อนด้วยสำเนาตามความลึก (ฐานมีแค่ 30 ช่อง คัดลอกถูกกว่าจดทุกการแก้)
void dfs(int v, int l, int r, int dep) {
    int keep = stk.size();
    int* bs = basis[dep];
    for (auto& e : node[v]) unite(e.x, e.y, e.w, bs);
    if (l == r) {
        if (qx[l]) {
            int dx, dy;
            find(qx[l], dx); find(qy[l], dy);
            int val = dx ^ dy;
            // ลดค่าจากบิตสูงลงต่ำ: ถ้า xor กับตัวในฐานแล้วเล็กลงก็เอา
            for (int b = B - 1; b >= 0; b--) val = min(val, val ^ bs[b]);
            cout << val << "\n";
        }
    } else {
        int m = (l + r) / 2;
        copy(bs, bs + B, basis[dep + 1]);
        dfs(2 * v, l, m, dep + 1);
        copy(bs, bs + B, basis[dep + 1]);
        dfs(2 * v + 1, m + 1, r, dep + 1);
    }
    rollback(keep);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m;
    map<pair<int, int>, pair<int, int>> open;  // (x, y) -> (น้ำหนัก, เวลาที่เริ่มมี)
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        open[{x, y}] = {w, 0};
    }
    cin >> q;
    // เวลา t = 0..q-1 คือคำสั่งลำดับที่ t เส้นที่ถูกเพิ่มที่เวลา t มีผลตั้งแต่ t
    // เส้นที่ถูกลบที่เวลา t มีผลถึง t-1
    for (int t = 0; t < q; t++) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            int w;
            cin >> w;
            open[{x, y}] = {w, t};
        } else if (type == 2) {
            auto it = open.find({x, y});
            if (it->second.second <= t - 1)
                addRange(1, 0, q - 1, it->second.second, t - 1, {x, y, it->second.first});
            open.erase(it);
        } else {
            qx[t] = x; qy[t] = y;
        }
    }
    for (auto& [key, val] : open)
        addRange(1, 0, q - 1, val.second, q - 1, {key.first, key.second, val.first});
    for (int i = 1; i <= n; i++) { par[i] = i; sz[i] = 1; }
    dfs(1, 0, q - 1, 0);  // basis[0] เริ่มว่างทั้งแถว
}