Problem: There are n rabbits, one in each of the huts numbered 0 through n − 1.

At one point, information came to the rabbits that a secret organization would be constructing an underground passage. The underground passage would allow the rabbits to visit other rabbits' huts. I'm happy.

The passages can go in both directions, and the passages do not intersect. Due to various circumstances, the passage once constructed may be destroyed. The construction and destruction of the passages are carried out one by one, and each construction It is assumed that the rabbit stays in his hut.

Rabbits want to know in advance if one rabbit and one rabbit can play at some stage of construction. Rabbits are good friends, so they are free to go through other rabbit huts when they go out to play. Rabbits who like programming tried to solve a similar problem in the past, thinking that it would be easy, but they couldn't write an efficient program. Solve this problem instead of the rabbit.



Input

The first line of input is given n and k separated by spaces. 2 ≤ n ≤ 40 000, 1 ≤ k ≤ 40 000

In the following k lines, construction information and questions are combined and given in chronological order.

* “1 u v” — A passage connecting huts u and v is constructed. Appears only when there is no passage connecting huts u and v.
* “2 u v” — The passage connecting huts u and v is destroyed. Appears only when there is a passage connecting huts u and v.
* “3 u v” — Determine if the rabbits in the hut u and v can be played.



0 ≤ u <v <n

Output

For each question that appears in the input, output "YES" if you can play, or "NO" if not.

Example

Input

4 10
1 0 1
1 0 2
3 1 2
2 0 1
1 2 3
3 0 1
1 0 1
2 0 2
1 1 3
3 0 2


Output

YES
NO
YES

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

#define DEBUG_MODE
#ifdef DEBUG_MODE
#define dump(x) cout << #x << " : " << x << endl
#define LINE cout << "line : " << __LINE__ << endl
#define dumpV(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << endl
#define STOP assert(false)
#else
#define dump(x) ;
#define LINE     ;
#define dumpV(v);
#define STOP     ;
#endif
#define mp make_pair

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fi<<", "<<a.se<<')';
    return out;
  }
}


struct UFT{    //O(loga(n))
    int n;
    vi d, r;
    UFT(int n) : n(n), d(n, -1), r(n, 0){};
    void init() {
        rep(i, n) d[i] = -1, r[i] = 0;
    }
    int root(int i){
        if(d[i] < 0) return i;
        return d[i] = root(d[i]);
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    bool unite(int x, int y){
        x = root(x);
        y = root(y);
        if(x == y) return false;

        if(r[x] < r[y]) swap(x, y);
        else if(r[x] == r[y]) r[x]++;
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    int size(int i){
        return -d[root(i)];
    }
};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    using Q = array<int, 4>;
    vector<Q> qs(k);
    rep(i, k) {
        cin >> qs[i][0] >> qs[i][1] >> qs[i][2];
        qs[i][3] = INF;
    }
    {
        map<int, stack<int>> mp;
        rep(i, k) {
            const auto& q = qs[i];
            auto j = q[1] * n + q[2];
            if(q[0] == 1) mp[j].push(i);
            else if(q[0] == 2) {
                int id = mp[j].top(); mp[j].pop();
                qs[id][3] = i;
            }
        }
    }

    // rep(i, k) {
    //     cout << i << " " << qs[i][0] << " " << qs[i][1] << " " << qs[i][2] << " " << qs[i][3] << endl;
    // }
    // cout << endl;

    int sqrtK = sqrt(k) + 1;
    for(int l = 0; l < k; l += sqrtK) {
        int r = min(k, l + sqrtK);
        UFT uf(n);
        {   // UFINIT
            REP(i, 0, l) if(qs[i][0] == 1 && qs[i][3] >= r) uf.unite(qs[i][1], qs[i][2]);
            //REP(i, r, k) if(qs[i][0] == 1 && qs[i][3] >= r) uf.unite(qs[i][1], qs[i][2]);
        }
        vector<int> root(n);
        rep(i, n) root[i] = uf.root(i);
        vector<multiset<int>> es(n);

        REP(i, 0, l) {
            if(qs[i][0] == 1 && qs[i][3] >= l) {
                auto u = root[qs[i][1]], v = root[qs[i][2]];
                if(u != v) {
                    es[u].insert(v);
                    es[v].insert(u);
                }
            }
        }

        // cout << "change SqrtK !";
        // rep(i, n) {
        //     cout << " " << root[i];
        // } 
        // cout << endl;
        // rep(i, n) {
        //     cout << i << " " ;dumpV(es[i]);
        // }

        auto check = [&](int u, int v) {
            set<int> used;
            queue<int> q;
            q.push(u);
            used.insert(u);
            while(!q.empty()) {
                auto p = q.front(); q.pop();
                for(auto&& to : es[p]) {
                    if(!used.count(to)) {
                        used.insert(to);
                        q.push(to);
                    }
                }
            }
            return used.count(v);
        };

        REP(i, l, r) {
            const auto& q = qs[i];
            // cout << " " << i << " " << q[0] << " " << q[1] << " " << q[2] << " " << q[3] << endl;
            const int u = root[q[1]], v = root[q[2]];
            // cout << " " << u << " " << v << endl;
            string ans = "not query";
            if(q[0] == 1) {
                if(u != v) {
                    es[u].insert(v);
                    es[v].insert(u);
                }
            }
            else if(q[0] == 2) {
                // assert(es[u].count(v) == es[v].count(u));
                // assert(es[u].count(v));
                // assert(es[v].count(u));
                if(u != v) {
                    es[u].erase(es[u].lower_bound(v));
                    es[v].erase(es[v].lower_bound(u));
                }
            }
            else {
                if(u == v || check(u, v)) ans = "YES";
                else ans = "NO";
                cout << ans << '\n';
            }
            // {
            //     vector<string> s{"unie", "remove", "query"};
            //     cout << " " << i << " " << s[q[0]-1] << ": " << q[1] << " ("  << root[q[1]] << ") "<< q[2] << "(" << root[q[2]] << ") => " << ans << endl;
            //     if(q[0] != 3) {
            //         rep(i, n) {
            //             rep(j, n) {
            //                 cout << " " << check(root[i], root[j]);
            //             }
            //             cout << endl;
            //         }
            //     }
            // }
        }
    }
    return 0;
}