Problem 56: Offline Dynamic Connectivity

Problem Statement: Given an undirected graph with n nodes and q queries of two types (add edge and remove edge) and connectivity queries, answer all connectivity queries offline.

Input

The first line contains n and q. Each of the next q lines starts with a type: 1 u v (add edge), 2 u v (remove edge), or 3 u v (check if u and v are connected). Initially, the graph is empty.

Output

For each query of type 3, print "YES" if u and v are connected by the current set of edges, otherwise print "NO".

Examples


Input:
5 6
1 1 2
1 2 3
3 1 3
2 1 2
3 1 3
3 4 5

Output:
YES
NO
NO

Solution Explanation

This problem is solved using offline processing with a union-find data structure in combination with a segment tree or divide and conquer technique to simulate the lifetime of edges. Each edge addition and removal is processed in segments and connectivity queries are answered using union-find snapshots.

Solution in C++


#include 
#include 
using namespace std;

struct DSU {
    vector parent, size;
    vector> history;
    int comp;
    DSU(int n): parent(n+1), size(n+1, 1), comp(n) {
        for (int i = 0; i <= n; i++)
            parent[i] = i;
    }
    int find(int a) { return parent[a] == a ? a : find(parent[a]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        history.push_back({b, parent[b]});
        parent[b] = a;
        size[a] += size[b];
        comp--;
        return true;
    }
    void rollback(int checkpoint) {
        while(history.size() > checkpoint) {
            auto x = history.back();
            history.pop_back();
            int b = x.first;
            int par = x.second;
            size[parent[b]] -= size[b];
            parent[b] = par;
            comp++;
        }
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    return 0;
}