#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long
struct ki{
int x;
ki *l=0;
ki *r=0;
ki *p=0;
bool rev=0;
ki()=default;
ki(int v){x=v;}
void push(){
if(rev){
rev=0;
swap(l,r);
if(l)l->rev^=1;
if(r)r->rev^=1;
}
}
bool adam(){
return p==0||(p->l!=this&&p->r!=this);
}
};
struct LCT{
vector<ki>a;
LCT(int n){
a.resize(n+1);
for(int i=1;i<=n;i++){
a[i].x=i;
}
}
void rot(ki *x){// literaly swaped father and son
auto p=x->p;
auto gp=p->p;
if(!p->adam()){
if(gp->r==p){
gp->r=x;
}
else{
gp->l=x;
}
}
p->push();
x->push();
if(p->l==x){
p->l=x->r;
x->r=p;
if(p->l)p->l->p=p;
}
else{
p->r=x->l;
x->l=p;
if(p->r)p->r->p=p;
}
p->p=x;
x->p=gp;
}
void splay(ki *x){ // i am the grand ,literaly how i understand
while(!x->adam()){
auto p=x->p;
auto gp=p->p;
if(!p->adam())rot((gp->r==p)==(p->r==x)?p:x);
rot(x);
}
x->push();
}
ki *access(int v){
ki *last=0;
ki *x=&a[v];
for(ki *p=x;p;p=p->p){
splay(p);
p->r=last;
last=p;
}
splay(x);
return last;
}
void make_root(int v){
access(v);
ki *x=&a[v];
if(x->l)x->l->rev^=1,x->l=0;
}
void merge(int x,int y){
make_root(y);
ki *v=&a[y];
v->p=&a[x];
}
void cut(int x,int y){
make_root(x);
access(y);
if(a[y].l){
a[y].l->p=0;
a[y].l=0;
}
}
bool same(int x,int y){
access(x);
access(y);
return a[x].p;
}
};
int n,q;
vector<int> simulateCollapse(int _n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) {
n=_n;
q=W.size();
vector<int>ans(q,0);
for(int i=0;i<q;i++){
LCT lc(n);
ans[i]=n;
for(int j=0;j<W[i];j++){
if(X[j]>Y[j])swap(X[j],Y[j]);
if(X[j]<=P[i]&&P[i]+1<=Y[j]){
continue;
}
if(T[j]==0){
if(!lc.same(X[j]+1,Y[j]+1)){
ans[i]--;
}
lc.merge(X[j]+1,Y[j]+1);
}
else{
lc.cut(X[j]+1,Y[j]+1);
if(!lc.same(X[j]+1,Y[j]+1)){
ans[i]++;
}
}
}
}
return ans;
}
