683. B (DSU RollBack)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

constexpr int INF = (int)1e18;
constexpr int N = (int)5e5 + 111;
constexpr int md = (int)1e9+7;

int parent[N];
int sz[N];
vector<pair<pair<int,int>,pair<int,int>>> history;
int deep[N];

int get(int x){
    if(parent[x] == x)
        return x;
    return get(parent[x]);
}

void union_sets(int a,int b){
    a = get(a), b = get(b);
    if(a == b){
        history.pb({{0,0},{0,0}});
        return;
    }
    if(deep[a] > deep[b])
        swap(a,b);
    history.pb(mp(mp(a,parent[a]),mp(sz[b],deep[b])));
    deep[b] = max(deep[b],deep[a]+1);
    parent[a] = b;
    sz[b] += sz[a];
    return;
}

bool connected(int a,int b){
    return get(a) == get(b);
}

void roll_back(){
    assert(!history.empty());
    int a = history.back().first.first, b = history.back().first.second, prevSZ = history.back().second.first;
    int d = history.back().second.second;
    history.pop_back();
    sz[parent[a]] = prevSZ;
    deep[parent[a]] = d;
    parent[a] = b;
    return;
}
vector<pair<int,int>> t[4*N];
void upd(int v,int l,int r,int tl,int tr,pair<int,int>& x){
    if(l > r || tl > tr)
        return;
    if(l == tl && r == tr){
        t[v].pb(x);
        return;
    }
    int m = (l+r)>>1;
    upd(v<<1,l,m,tl,min(tr,m),x);
    upd(v<<1|1,m+1,r,max(tl,m+1),tr,x);
    return;
}

vector<int> g[N];
vector<pair<int,int>> edges;
map<pair<int,int>,int> pr;

struct query{
    int id,x,y;
    int a = -1, b = -1;
    query(){}
    query(int x,int y,int id):x(x),y(y),id(id){}
    query(int x,int y,int a,int b,int id):x(x),y(y),a(a),b(b),id(id){}
};

vector<query> QueriesSec[N];
vector<query> QueryEdge;

bool ans[N];
vector<pair<int,int>> current;

void go(int v,int l,int r){
    for(auto&[x,y] : t[v]){
//        cerr << "adding " << x << " " << y << "\n";
        union_sets(x,y);
//        current.pb(mp(x,y));
    }
    if(l == r){
//        cerr << "l,r = " << l << " " << r << "\n";
//        for(auto&[x,y] : current){
//            cerr << x << " " << y << "\n";
//        }
//        cerr << "\n";
        for(auto& q : QueriesSec[l]){
            int& id = q.id, x = q.x, y = q.y;
            ans[id] = connected(x,y);
//            cerr << "x,y = " << x << " " << y << "\n";
        }
    } else {
        int m = (l+r)>>1;
        go(v<<1,l,m);
        go(v<<1|1,m+1,r);
    }
    for(auto&[x,y] : t[v]){
//        cerr << "removing " << x << " " << y << "\n";
        roll_back();
//        current.pop_back();
    }
    return;
}

void solve(){
    int n,m;
    cin >> n >> m;

    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        if(a > b)
            swap(a,b);
        edges.pb(mp(a,b));
        g[a].pb(b);
        g[b].pb(a);
    }

    for(int i = 1; i <= n; i++){
        for(auto& to : g[i]){
            int a = i, b = to;
            if(a > b)
                swap(a,b);
            pair<int,int> e = mp(a,b);
            upd(1,1,n,pr[mp(a,b)]+1,i-1,e);
            pr[mp(a,b)] = i;
        }
    }

    for(int i = 0; i < N; i++){
        parent[i] = i;
        deep[i] = 1;
    }

    for(auto& x : edges){
        upd(1,1,n,pr[x]+1,n,x);
    }
    int q;
    cin >> q;

    for(int i = 1; i <= q; i++){
        int tp;
        cin >> tp;
        int x,y;
        cin >> x >> y;
        if(tp == 1){
            int a,b;
            cin >> a >> b;
            QueryEdge.pb(query(x,y,a,b,i));
        } else {
            int a;
            cin >> a;
            QueriesSec[a].pb(query(x,y,i));
        }
    }

    go(1,1,n);
//    for(int i = 1; i <= q; i++)
//        cerr << (ans[i] ? "Yes" : "No") << "\n";
//    cerr << "\n";
//    return;

    pr.clear();

    for(int i = 0; i < 4*N; i++){
        t[i].clear();
    }
    for(int i = 0; i < N; i++){
        QueriesSec[i].clear();
    }

    int i = 1;
    int sz = QueryEdge.size()+1;
    for(int i = 0; i < N; i++){
        parent[i] = i;
        deep[i] = 1;
    }
    assert(history.empty());
    history.clear();

    for(auto& q : QueryEdge){
        QueriesSec[i].pb(q);
        int& a = q.a, b = q.b;
        if(a > b)
            swap(a,b);
        pair<int,int> e = mp(a,b);
        upd(1,1,sz,pr[e]+1,i-1,e);
        pr[e] = i++;
    }

    for(auto& x : edges){
        upd(1,1,sz,pr[x]+1,sz,x);
    }

    go(1,1,sz);

    for(int i = 1; i <= q; i++){
        cout << (ans[i] ? "yes" : "no") << "\n";
    }

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
        solve();
    }
    return 0;
}
/**
no
yes
yes
no
yes
yes
yes
yes
yes
yes
yes
no
yes
yes
yes
no
yes
yes

**/