ดิสจอยต์เซต: รู้ในพริบตาว่าสองคนอยู่ก๊วนเดียวกันไหม แม้ก๊วนจะรวมกันไปแล้วเป็นแสนครั้ง

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

const int MAXN = 100005;
int par[MAXN], sz[MAXN];

int find(int x) {
    // บีบทางเดิน: ทุกตัวบนทางชี้ตรงไปหาหัวก๊วน รอบหน้าเดินก้าวเดียวก็ถึง
    return par[x] == x ? x : par[x] = find(par[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);        // เอาก๊วนเล็กไปห้อยใต้ก๊วนใหญ่ ต้นไม้จึงสูงไม่เกิน log n
    par[b] = a;
    sz[a] += sz[b];
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;

    int comps = n, best = 1;               // เริ่มแต่ละเมืองเป็นก๊วนเดี่ยว ขนาด 1
    while (m--) {
        int a, b;
        cin >> a >> b;
        if (unite(a, b)) {
            comps--;
            // ก๊วนจะโตได้ก็ตอนรวมเท่านั้น จึงเช็กแค่ก๊วนที่เพิ่งรวมก็พอ
            best = max(best, sz[find(a)]);
        }
        cout << comps << ' ' << best << '\n';
    }
    return 0;
}

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

const int MAXN = 1005;
int par[MAXN], sz[MAXN];

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[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];
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;

    // ถนนที่ unite ไม่สำเร็จคือถนนที่ปิดวงรอบ ปิดทิ้งได้โดยไม่มีใครขาดจากกัน
    vector<pair<int, int>> extra;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        if (!unite(a, b)) extra.push_back({a, b});
    }

    // หัวของทุกก๊วน: มีถนน n-1 เส้น เสียไป k เส้น จึงเหลือก๊วนพอดี k+1 ก๊วน
    vector<int> heads;
    for (int i = 1; i <= n; i++)
        if (find(i) == i) heads.push_back(i);

    cout << extra.size() << '\n';
    for (size_t i = 0; i < extra.size(); i++)
        // ใช้ถนนเกินเส้นที่ i ต่อก๊วนแรกเข้ากับก๊วนที่ i+1 ทุกก๊วนจึงถูกต่อครั้งเดียว ไม่เกิดวงรอบใหม่
        cout << extra[i].first << ' ' << extra[i].second << ' '
             << heads[0] << ' ' << heads[i + 1] << '\n';
    return 0;
}

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

const int MAXN = 100005;
int par[MAXN], sz[MAXN];

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[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];
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> roads(m);                // {ค่าซ่อม, a, b} ใส่ค่าซ่อมไว้หน้าสุดเพื่อให้ sort เรียงตามราคา
    for (auto& [c, a, b] : roads) cin >> a >> b >> c;
    sort(roads.begin(), roads.end());
    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;

    ll total = 0;                                   // n-1 เส้น เส้นละ 1e9 เกิน int ได้
    int used = 0;
    for (auto& [c, a, b] : roads)
        // ถูกสุดก่อน และซ่อมเฉพาะเส้นที่ต่อสองก๊วนที่ยังแยกกัน เส้นที่ปิดวงรอบมีเส้นที่ถูกกว่าทำงานแทนไปแล้ว
        if (unite(a, b)) total += c, used++;

    if (used == n - 1) cout << total << '\n';
    else cout << "IMPOSSIBLE\n";                    // ซ่อมครบทุกเส้นที่ช่วยได้แล้วยังไม่ถึง n-1 แปลว่ากราฟขาดจากกันตั้งแต่ต้น
    return 0;
}

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

vector<int> par, sz;
int comps; // จำนวนชิ้นของใยตอนนี้

int find(int x) {
    // บีบทางเดิน: ให้ทุกตัวบนทางชี้ตรงไปที่หัวหน้า
    return par[x] == x ? x : par[x] = find(par[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];
    comps--;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> ea(m + 1), eb(m + 1);
    for (int i = 1; i <= m; i++) cin >> ea[i] >> eb[i];
    int q;
    cin >> q;
    vector<int> tear(q);
    vector<bool> torn(m + 1, false);
    for (int i = 0; i < q; i++) {
        cin >> tear[i];
        torn[tear[i]] = true;
    }

    par.resize(n + 1);
    sz.assign(n + 1, 1);
    iota(par.begin(), par.end(), 0);
    comps = n;

    // เริ่มจากสภาพสุดท้าย: ใส่เฉพาะเส้นที่ไม่มีวันถูกฉีก
    for (int i = 1; i <= m; i++)
        if (!torn[i]) unite(ea[i], eb[i]);

    // ย้อนเวลา: ans[i] คือสภาพหลังฉีกครั้งที่ 0..i
    // ถอยจากท้ายมา การ "ฉีกเส้น tear[i]" กลายเป็น "ต่อเส้น tear[i] กลับ"
    // ต่อกลับแล้วจะได้สภาพก่อนฉีกครั้งที่ i ซึ่งก็คือหลังฉีกครั้งที่ i-1
    vector<int> ans(q);
    ans[q - 1] = comps;
    for (int i = q - 1; i > 0; i--) {
        unite(ea[tear[i]], eb[tear[i]]);
        ans[i - 1] = comps;
    }

    for (int i = 0; i < q; i++) cout << ans[i] << (i + 1 < q ? ' ' : '\n');
    return 0;
}

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

vector<int> par, sz, d; // d[x] = ความเป็นคู่/คี่ของ pre[x] xor pre[par[x]]

int find(int x) {
    if (par[x] == x) return x;
    int r = find(par[x]);
    d[x] ^= d[par[x]]; // ตอนนี้ d[par[x]] คือระยะจากแม่ถึงหัวหน้าแล้ว
    par[x] = r;
    return r;
}

// บันทึกว่า pre[a] xor pre[b] = w  คืน false ถ้าขัดกับที่รู้มาก่อน
bool unite(int a, int b, int w) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return (d[a] ^ d[b]) == w;
    if (sz[ra] < sz[rb]) swap(ra, rb); // สลับหัวหน้าได้ เพราะ xor สลับข้างได้
    par[rb] = ra;
    d[rb] = d[a] ^ d[b] ^ w;           // pre[rb] xor pre[ra] ที่ทำให้เงื่อนไขนี้จริง
    sz[ra] += sz[rb];
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long len;
    while (cin >> len && len != -1) {
        int q;
        cin >> q;
        vector<long long> lo(q), hi(q);
        vector<int> w(q);
        vector<long long> xs;
        for (int i = 0; i < q; i++) {
            string s;
            cin >> lo[i] >> hi[i] >> s;
            lo[i]--; // ช่วง [l, r] มีเลขคี่ตัว  <=>  pre[r] xor pre[l-1] = 1
            w[i] = (s == "odd");
            xs.push_back(lo[i]);
            xs.push_back(hi[i]);
        }
        // ความยาวถึง 10^9 แต่มีจุดที่ถูกพูดถึงไม่เกิน 2q จุด
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        int k = xs.size();
        par.resize(k);
        iota(par.begin(), par.end(), 0);
        sz.assign(k, 1);
        d.assign(k, 0);

        int ans = q; // ถ้าไม่มีข้อไหนขัด คำตอบคือจำนวนคำถามทั้งหมด
        for (int i = 0; i < q; i++) {
            int a = lower_bound(xs.begin(), xs.end(), lo[i]) - xs.begin();
            int b = lower_bound(xs.begin(), xs.end(), hi[i]) - xs.begin();
            if (!unite(a, b, w[i])) {
                ans = i; // ข้อ 0..i-1 ยังเป็นไปได้ ข้อที่ i พัง
                break;   // คำถามที่เหลืออ่านมาครบแล้ว หยุดได้เลย
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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

const int MAXN = 300005;
// find(i) = อัศวินหมายเลขน้อยสุดที่ >= i และยังไม่แพ้ (ถ้าไม่มีเลย จะได้ n+1)
int par[MAXN];

// ข้อนี้รวมตามขนาดไม่ได้ (คนแพ้ต้องชี้ไปทางขวาเสมอ) โซ่จึงยาวได้เป็นแสนช่อง
// find แบบเรียกตัวเองจะล้นสแต็ก เลยเขียนเป็นสองรอบ: รอบแรกหาหัว รอบสองให้ทุกตัวบนทางชี้ตรงไปที่หัว
int find(int x) {
    int root = x;
    while (par[root] != root) root = par[root];
    while (par[x] != root) {
        int next = par[x];
        par[x] = root;
        x = next;
    }
    return root;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n + 1; i++) par[i] = i;   // n+1 เป็นกำแพงท้ายแถว find จะไม่วิ่งเลยออกไป
    vector<int> beat(n + 1, 0);

    while (m--) {
        int l, r, x;
        cin >> l >> r >> x;
        // กระโดดข้ามคนที่แพ้ไปแล้วทั้งหมด แตะเฉพาะคนที่ยังอยู่ในช่วง
        for (int i = find(l); i <= r; i = find(i + 1)) {
            if (i == x) continue;                  // ผู้ชนะยังอยู่ต่อ
            beat[i] = x;
            par[i] = i + 1;                        // แพ้แล้ว ชี้ไปทางขวา ใครมาถามก็ถูกส่งต่อ
        }
    }
    for (int i = 1; i <= n; i++) cout << beat[i] << " \n"[i == n];
    return 0;
}

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

const int MAXN = 300005;
// find(i) = อัศวินหมายเลขน้อยสุดที่ >= i และยังไม่แพ้ (ถ้าไม่มีเลย จะได้ n+1)
int par[MAXN];

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);   // ผิดตรงนี้: เรียกตัวเองลึกเท่าความยาวโซ่ โซ่ยาวแสนช่องล้นสแต็กเริ่มต้นของ Windows
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n + 1; i++) par[i] = i;   // n+1 เป็นกำแพงท้ายแถว find จะไม่วิ่งเลยออกไป
    vector<int> beat(n + 1, 0);

    while (m--) {
        int l, r, x;
        cin >> l >> r >> x;
        // กระโดดข้ามคนที่แพ้ไปแล้วทั้งหมด แตะเฉพาะคนที่ยังอยู่ในช่วง
        for (int i = find(l); i <= r; i = find(i + 1)) {
            if (i == x) continue;                  // ผู้ชนะยังอยู่ต่อ
            beat[i] = x;
            par[i] = i + 1;                        // แพ้แล้ว ชี้ไปทางขวา ใครมาถามก็ถูกส่งต่อ
        }
    }
    for (int i = 1; i <= n; i++) cout << beat[i] << " \n"[i == n];
    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<set<int>> s(n + 1); // s[v] = สีทั้งหมดในต้นย่อยของ v (สร้างเสร็จเมื่อลูกทุกตัวรวมเข้ามาแล้ว)
    for (int v = 1; v <= n; v++) {
        int c;
        cin >> c;
        s[v].insert(c);
    }
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // เรียงจุดแบบ BFS จากราก ลูกจะอยู่หลังพ่อเสมอ
    // ไล่จากท้ายมาจึงได้ทำลูกครบก่อนพ่อ โดยไม่ต้อง DFS เวียนเกิดลึก 2*10^5 ชั้น
    vector<int> order, parent(n + 1, 0);
    order.reserve(n);
    order.push_back(1);
    for (int i = 0; i < n; i++) {
        int u = order[i];
        for (int v : g[u])
            if (v != parent[u]) parent[v] = u, order.push_back(v);
    }

    vector<int> ans(n + 1);
    for (int i = n - 1; i >= 0; i--) {
        int v = order[i];
        ans[v] = s[v].size();
        int p = parent[v];
        if (p == 0) continue; // ราก ไม่มีใครให้รวมเข้า
        // รวมเล็กเข้าใหญ่: ให้ s[p] เป็นก้อนที่ใหญ่กว่าเสมอ แล้วเทก้อนเล็กใส่
        // swap ของ set แค่สลับตัวชี้ ไม่ได้คัดลอกสมาชิก
        if (s[p].size() < s[v].size()) swap(s[p], s[v]);
        for (int c : s[v]) s[p].insert(c);
        set<int>().swap(s[v]); // คืนหน่วยความจำ ต้นย่อยนี้ตอบไปแล้ว
    }

    for (int v = 1; v <= n; v++) cout << ans[v] << (v < n ? ' ' : '\n');
    return 0;
}

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

// ชนิดสัตว์เป็น 0, 1, 2 และ x กิน y  <=>  ชนิด(y) = ชนิด(x) + 1 (มอดุโล 3)
// d[x] = ชนิด(x) - ชนิด(par[x]) มอดุโล 3  (0 = พวกเดียวกับแม่, 1 = แม่กิน x, 2 = x กินแม่)
vector<int> par, sz, d;

int find(int x) {
    if (par[x] == x) return x;
    int r = find(par[x]);
    d[x] = (d[x] + d[par[x]]) % 3; // ต่อระยะ x ถึงแม่ กับแม่ถึงหัวหน้า
    par[x] = r;
    return r;
}

// บันทึกว่า ชนิด(y) - ชนิด(x) = w (มอดุโล 3)  คืน false ถ้าขัดกับที่เชื่อไปแล้ว
bool unite(int x, int y, int w) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return ((d[y] - d[x]) % 3 + 3) % 3 == w;
    // ให้ ry ไปห้อยใต้ rx: ชนิด(ry) - ชนิด(rx) = d[x] + w - d[y]
    int t = ((d[x] + w - d[y]) % 3 + 3) % 3;
    if (sz[rx] < sz[ry]) {
        swap(rx, ry);
        t = (3 - t) % 3; // มองกลับด้าน ความต่างก็กลับเครื่องหมาย
    }
    par[ry] = rx;
    d[ry] = t;
    sz[rx] += sz[ry];
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        par.resize(n + 1);
        iota(par.begin(), par.end(), 0);
        sz.assign(n + 1, 1);
        d.assign(n + 1, 0);
        int lies = 0;
        for (int i = 0; i < k; i++) {
            int D, x, y;
            cin >> D >> x >> y;
            // เงื่อนไขโกหกสองข้อแรก ต้องเช็คก่อนแตะ DSU (x หรือ y อาจเกิน n)
            if (x > n || y > n || (D == 2 && x == y)) {
                lies++;
                continue;
            }
            // D = 1 พวกเดียวกัน ความต่าง 0  /  D = 2 x กิน y ความต่าง 1
            if (!unite(x, y, D - 1)) lies++; // ประโยคที่ขัดไม่ถูกบันทึก เพราะมันไม่ใช่ความจริง
        }
        cout << lies << '\n';
    }
    return 0;
}