#pragma once
#include <vector>
#include <utility>

struct DSU {
    std::vector<int> dsu_parent;
    std::vector<int> dsu_rank;

    DSU() {}
    explicit DSU(int n) { init(n); }

    void init(int n) {
        dsu_parent.resize(n + 1);
        dsu_rank.assign(n + 1, 0);
        for (int i = 0; i <= n; ++i) dsu_parent[i] = i;
    }

    int find(int x) {
        while (dsu_parent[x] != x) {
            dsu_parent[x] = dsu_parent[dsu_parent[x]];
            x = dsu_parent[x];
        }
        return x;
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (dsu_rank[a] < dsu_rank[b]) std::swap(a, b);
        dsu_parent[b] = a;
        if (dsu_rank[a] == dsu_rank[b]) ++dsu_rank[a];
        return true;
    }

    bool same(int a, int b) { return find(a) == find(b); }
};