#pragma once
#include <algorithm>
#include <vector>

struct UnionFind {
    std::vector<int> par, rank_, sz;

    explicit UnionFind(int n) : par(n), rank_(n, 0), sz(n, 1) {
        for (int i = 0; i < n; ++i) par[i] = i;
    }

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

    int unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return -1;
        if (rank_[a] < rank_[b]) std::swap(a, b);
        par[b] = a;
        sz[a] += sz[b];
        if (rank_[a] == rank_[b]) ++rank_[a];
        return a;
    }
};