题意
板子题，题意很清楚吧。。
Sol
很显然可以直接上LCT。。
但是这题允许离线，于是就有了一个非常巧妙的离线的做法，好像叫什么线段树分治？？
此题中每条边出现的位置都可以看做是一段区间。
我们用线段树维护。线段树的每个节点维护一个vector表示覆盖了当前节点的边的存在区间
因为总的边数是$M$的，因此线段树内总的元素最多为$logM * M$，空间可以保证
输出答案的话需要最后dfs一遍
用并查集维护出当前联通的点，需要支持撤销操作。
方法是通过按秩合并保证复杂度，不带路径压缩。
这样的话每次断父亲就行了。
我看题解里面的按秩合并都是按度数合并的，我试了一下按节点大小合并，发现跑的差不多快。。
/*
线段树分治
对于维护每一个操作出现的区间
并查集维护连通性，维护的时候记录度数，按秩合并
撤销的时候把度数小的撤销掉。
*/
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = * 1e6 + ;
inline int read() {
char c = getchar(); int x = , f = ;
while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
int N, M;
int tim[][];//边(i, j)加入的时间
int fa[MAXN];
struct Node {
int x, deg;
}S[MAXN];
struct Query {
int opt, x, y;
}Q[MAXN];
#define ls k << 1
#define rs k << 1 | 1
struct SegTree {
int l, r;
vector<int> id;
}T[MAXN];
void Build(int k, int ll, int rr) {
T[k] = (SegTree) {ll, rr};
if(ll == rr) return ;
int mid = ll + rr >> ;
Build(ls, ll, mid); Build(rs, mid + , rr);
}
void IntervalAdd(int k, int ll, int rr, int val) {
if(ll <= T[k].l && T[k].r <= rr) {T[k].id.push_back(val); return ;}
int mid = T[k].l + T[k].r >> ;
if(ll <= mid)IntervalAdd(ls, ll, rr, val);
if(rr > mid)IntervalAdd(rs, ll, rr, val);
}
int Top, inder[MAXN];
int find(int x) {
if(fa[x] == x) return x;
else return find(fa[x]);
}
void unionn(int x, int y) {
x = find(x); y = find(y);
if(x == y) return;
if(inder[x] < inder[y]) swap(x, y);
fa[y] = x;
S[++Top] = (Node) {y, inder[y]};
if(inder[x] == inder[y]) S[++Top] = (Node) {x, inder[x] = inder[x] + inder[y]};//tag
}
void Delet(int cur) {
while(Top > cur) {
Node pre = S[Top--];
fa[pre.x] = pre.x;
inder[pre.x] = pre.deg;
}
}
void dfs(int k) {
int cur = Top;
for(int i = ; i < T[k].id.size(); i++) unionn(Q[T[k].id[i]].x, Q[T[k].id[i]].y);
if(T[k].l == T[k].r) {
if(Q[T[k].l].opt == )
putchar(find(Q[T[k].l].x) == find(Q[T[k].l].y) ? 'Y' : 'N'), putchar('\n');
} else dfs(ls), dfs(rs); Delet(cur);
}
int main() {
N = read(); M = read();
for(int i = ; i <= N; i++) fa[i] = i, inder[i] = ;
Build(, , M);//按时间为下标建线段树
for(int i = ; i <= M; i++) {
int opt = read(), x = read(), y = read();
if(x > y) swap(x, y);
if(opt == ) tim[x][y] = i;
if(opt == ) IntervalAdd(, tim[x][y], i, i), tim[x][y] = ;
Q[i] = (Query) {opt, x, y};
}
for(int i = ; i <= N; i++)
for(int j = i; j <= N; j++)
if(tim[i][j])
IntervalAdd(, tim[i][j], M, tim[i][j]);
dfs();
return ;
}