Submission #19560092

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/dsu>
using namespace atcoder;
using ll = long long;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a) (a).begin(),(a).end()
void Main(){
    int n, m, q;
    cin >> n >> m;
    vector<int> a(m), b(m);
    For(i,0,m) cin >> a[i] >> b[i];
    cin >> q;
    vector<int> x(q), y(q), ng(q, 0), ok(q, m);
    vector<vector<int>> mid(m+1);
    For(i,0,q) cin >> x[i] >> y[i];
    For(i,0,q) mid[m/2].emplace_back(i);
    For(_,0,20){
        vector<vector<int>> nextmid(m+1);
        dsu uf(n+1);
        For(i,0,m){
            uf.merge(a[i], b[i]);
            for(auto query:mid[i]){
                if(uf.same(x[query], y[query])){
                    ok[query] = i;
                }
                else{
                    ng[query] = i;
                }
                nextmid[(ok[query] + ng[query]) / 2].emplace_back(query);
            }
        }
        swap(mid, nextmid);
    }
    For(i,0,q) cout << (ok[i] < m ? ok[i] + 1 : -1) << endl;
}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}

Submission Info

Judge Result