test/yukicoder/0416.test.cpp

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/416
#include <algorithm>
#include <cmath>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
#include "persistent_ds/partially_persistent_union_find.hpp"

int main(void) {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::pair<int, int>> es(m);
    for (auto &[a, b] : es) std::cin >> a >> b;
    std::vector<std::pair<int, int>> queries(q);
    for (auto &[a, b] : queries) std::cin >> a >> b;
    std::reverse(queries.begin(), queries.end());
    std::set<std::pair<int, int>> st(queries.begin(), queries.end());

    PartiallyPersistentUnionFind uf(n);
    for (auto [a, b] : es) {
        if (!st.count({a, b})) uf.unite(a - 1, b - 1);
    }
    for (auto [a, b] : queries) uf.unite(a - 1, b - 1);

    for (int i = 1; i < n; ++i) {
        if (!uf.same(0, i)) {
            std::cout << 0 << '\n';
            continue;
        }
        if (uf.same(0, i, m - q)) {
            std::cout << -1 << '\n';
            continue;
        }
        auto check = [&](int mid) { return !uf.same(0, i, m - mid); };
        int l = q, r = -1;
        while (std::abs(l - r) > 1) {
            int mid = (l + r) / 2;
            (check(mid) ? l : r) = mid;
        }
        std::cout << l << '\n';
    }

    return 0;
}