Submission #3426571

---

Source Code Expand

#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
class union_find{
    private:
        int n;
        vector<T> p, rank, time;
        int now;

    public:
        union_find(int n)
            : n(n), p(n+1, -1), rank(n+1), time(n+1, INF), now(0) {}

        int find(int v, int t){
            if(time[v] > t){
                return v;
            }

            return find(p[v], t);
        }

        int unite(int u, int v){
            ++now;
            int u_root = find(u, now);
            int v_root = find(v, now);

            if(u_root == v_root){
                return now;
            }

            if(rank[u_root] < rank[v_root]){
                swap(u_root, v_root);
            }

            if(rank[u_root] == rank[v_root]){
                rank[u]++;
            }

            p[v_root] = u_root;
            time[v] = now;
            return now;
        }
};

signed main(){
    int n, m;
    cin >> n >> m;

    union_find<int> uf(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        uf.unite(a, b);
    }

    int q;
    cin >> q;
    rep(i, q){
        int x, y;
        cin >> x >> y;

        int lo = -1;
        int hi = m + 1;
        while(hi - lo > 1){
            int mid = (lo + hi) / 2;
            int px = uf.find(x, mid);
            int py = uf.find(y, mid);

            if(px == py){
                hi = mid;
            }else{
                lo = mid;
            }
        }

        if(hi == m + 1){
            cout << -1 << endl;
        }else{
            cout << hi << endl;
        }
    }


    return 0;
}

Submission Info

Judge Result