//subtask3
#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;
const int sq = 320;
class DSU {
public:
int n,com;
int head[maxn], sz[maxn];
stack<pii> stk;
void init(int _n) {
n = com = _n;
for(int i=0;i<n;i++) {
head[i] = i;
sz[i] = 1;
}
}
int findhead(int x) {
if(x==head[x]) return x;
return findhead(head[x]);
}
void add_edge(int u, int v) {
int x = findhead(u), y = findhead(v);
if(sz[x] > sz[y]) swap(x,y);
stk.push({x,y});
if(x!=y) {
head[x] = y;
sz[y] += sz[x];
com--;
}
}
void pop_edge() {
int x = stk.top().X, y = stk.top().Y; stk.pop();
if(x!=y) {
head[x] = x;
sz[y] -= sz[x];
com++;
}
}
int size() {
return com;
}
} dsu;
struct trp {
int x,y,id;
};
int n,m,q;
int ft[maxn];
map<pii,int> occur;
vector<trp> op;
vector<int> good, amb;
vector<int> ask[maxn];
int ans[maxn];
bool cmpL(trp a, trp b) {
if(a.y != b.y) return a.y < b.y;
return a.id < b.id;
}
bool cmpR(trp a, trp b) {
if(a.x != b.x) return a.x > b.x;
return a.id < b.id;
}
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> D, vector<int> P) {
n = N; m = T.size(); q = D.size();
for(int i=0;i<m;i++) {
if(X[i]>Y[i]) swap(X[i],Y[i]);
if(T[i]==0) {
ft[i] = m-1;
occur[{X[i],Y[i]}] = i;
}
else ft[occur[{X[i],Y[i]}]] = i-1;
}
for(int i=0;i<q;i++) ask[D[i]].push_back(i);
for(int s=0;s<m;s+=sq) {
int e = min(m,s+sq-1);
//eliminate all invalid edge (ft[i] < s)
vector<int> tmp;
for(auto i : good) {
if(ft[i] < s) continue;
tmp.push_back(i);
}
good = tmp;
//---------------------------------------------------------------------------
op.clear(); amb.clear();
for(int i=s;i<=e;i++) {
for(auto x : ask[i]) op.push_back({P[x],P[x],x});
}
for(auto i : good) {
if(ft[i]>=e) op.push_back({X[i],Y[i],-1});
else amb.push_back(i);
}
for(int i=s;i<=e;i++) amb.push_back(i);
sort(op.begin(),op.end(),cmpL);
dsu.init(n);
for(auto t : op) {
int x = t.id;
if(x<0) dsu.add_edge(t.x,t.y);
else {
int ex = 0;
for(auto i : amb) {
if(Y[i]<=t.x && i<=D[x] && D[x]<=ft[i]) {
dsu.add_edge(X[i],Y[i]);
ex++;
}
}
ans[x] += dsu.size();
while(ex--) dsu.pop_edge();
}
}
//---------------------------------------------------------------------------
op.clear();
for(int i=s;i<=e;i++) {
for(auto x : ask[i]) op.push_back({P[x]+1,P[x]+1,x});
}
for(auto i : good) {
if(ft[i]>=e) op.push_back({X[i],Y[i],-1});
else amb.push_back(i);
}
sort(op.begin(),op.end(),cmpR);
dsu.init(n);
for(auto t : op) {
int x = t.id;
if(x<0) dsu.add_edge(t.x,t.y);
else {
int ex = 0;
for(auto i : amb) {
if(t.y<=X[i] && i<=D[x] && D[x]<=ft[i]) {
dsu.add_edge(X[i],Y[i]);
ex++;
}
}
ans[x] += dsu.size();
while(ex--) dsu.pop_edge();
}
}
//---------------------------------------------------------------------------
for(int i=s;i<=e;i++) {
if(T[i]==0) good.push_back(i);
}
}
vector<int> vec;
for(int i=0;i<q;i++) vec.push_back(ans[i]-n);
return vec;
}
