#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
struct dsu0 {
vector<int> par, siz;
int n;
int cc;
int largest;
void init(int n) {
assert(n>0);
this->n=n;
cc=n;
par.resize(n+10);siz.resize(n+10);
for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
largest=1;
}
int parent(int x) {
assert(x>=0 && x<n);
return par[x]==x?x:par[x]=parent(par[x]);
}
bool join(int x, int y) {
x=parent(x);y=parent(y);
if (x==y) return false;
cc--;
if (siz[x]<siz[y]) swap(x,y);
siz[x]+=siz[y];par[y]=x;
largest=max(largest,siz[x]);
return true;
}
};
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e5 + 5;
struct line {
int type, x, y;
line(int _t, int _x, int _y) : type(_t), x(_x), y(_y) {}
};
set<int> g[maxn];
set<pair<int,int>> edges;
void add_edge(int x, int y) {
if (x>y) swap(x,y);
g[x].insert(y);
g[y].insert(x);
edges.insert({x,y});
}
void rem_edge(int x, int y) {
if (x>y) swap(x,y);
g[x].erase(y);
g[y].erase(x);
edges.erase({x,y});
}
vector<int> solve(int N, vector<line> v, vector<vector<pair<int,int>>> ev, int Q) {
int n = v.size();
vector<int> ans(Q);
for (int i=0; i<n; i++) {
if (v[i].type==0) {
add_edge(v[i].x,v[i].y);
} else {
rem_edge(v[i].x,v[i].y);
}
for (auto qu: ev[i]) {
int id = qu.first;
int x = qu.second;
dsu0 dsu; dsu.init(N);
for (auto ed: edges) {
int u = ed.first;
int v = ed.second;
if (u<=x && x+1<=v) continue;
dsu.join(u,v);
}
ans[id] = dsu.cc;
}
}
return ans;
}
std::vector<int> simulateCollapse(
int N,
std::vector<int> T,
std::vector<int> X,
std::vector<int> Y,
std::vector<int> W,
std::vector<int> P
) {
int n = T.size();
vector<vector<pair<int,int>>> ev(n);
for (int i=0; i<(int)W.size(); i++) {
ev[W[i]].push_back({i,P[i]});
}
vector<line> v;
for (int i=0; i<n; i++) {
v.push_back({T[i],X[i],Y[i]});
}
return solve(N, v, ev, W.size());
}
