New Roads Queries

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ld long double
#define F first
#define S second
#define el '\n'
#define cout(x) for(auto v:x)cout<<v<<' ';cout<<el
#define coutp(x) for(auto v:x)cout<<v.F<<' '<<v.S<<el
#define cin(x) for(auto &v:x)cin>>v;
#define all(x)  x.begin(),x.end()
#define ll long long
#define sz(x)  (int)x.size()
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define vi vector<ll>
using ull = unsigned long long;
const int N=2e5+5;
vector<pi>adj[N];
ll t;
class DSU {
public:
    vector<int> parents;
    vector<int> sizes;
    DSU(int size) : parents(size), sizes(size, 1) {
        for (int i = 0; i < size; i++) {parents[i] = i;}
    }

    /** @return the "representative" node in x's component */
    int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

    /** @return whether the merge changed connectivity */
    bool unite(int x, int y) {
        int x_root = find(x);
        int y_root = find(y);
        if (x_root == y_root) { return false; }
        if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
        sizes[x_root] += sizes[y_root];
        parents[y_root] = x_root;
        return true;
    }
    bool connected(int x, int y) { return find(x) == find(y); }
};

void solve(){
ll n,m,q;
    cin>>n>>m>>q;
    vector<pi>edges(m+1);
    for (int i=1;i<=m;i++)
    {
        ll u,v;
        cin>>u>>v;
        edges[i]={u,v};
    }
    vector<pi>qe(q);
    for (int i=0;i<q;i++)
    {
        ll u,v;
        cin>>u>>v;
        qe[i]={u,v};
    }

    vector<ll>L(q,0),R(q,m),ans(q,-1);
    bool f=1;
    while(f)
    {
        f=0;

        vector<vi>buk(m+1);
        for (int i=0;i<q;i++)
        {
            if (L[i]<=R[i]){
            ll mid=(L[i]+R[i])/2;
            buk[mid].push_back(i);
                f=1;
            }
        }

        DSU ds(n+1);
        for (int t=0;t<=m;t++)
        {
            if (t>0)ds.unite(edges[t].first,edges[t].second);
            if (!buk[t].empty())
            {
                for (auto it:buk[t])
                {
                    if (ds.connected(qe[it].first,qe[it].second))R[it]=t-1,ans[it]=t;
                    else L[it]=t+1;
                }
            }
        }
    }

for (auto  it:ans)cout<<it<<"\n";
}


int32_t main()
{
#ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
     //freopen("output.txt", "w", stdout);
#endif



    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; i++)solve();
    return 0;
}
/*

 */