#include "collapse.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128; 
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii; 
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;

const int N=1e5+5;
int n,m,k,q,ans[N],b;
map<pii,pii>ed;
vi d[N],f[N]; vp g[N];

struct DSU {
  int id[N],cnt; vi p;
  void init() {cnt=0; rep(i,1,n) id[i]=i;}
  void init(vi p) {cnt=p.size(); for(int x:p) id[x]=x;}
  int find(int i) {return i==id[i]?i:id[i]=find(id[i]);}
  void merge(int x,int y) {
    x=find(x), y=find(y);
    if(x!=y) cnt--, id[x]=y;
  }
  int qry() {return cnt;}
} A,B;

struct edge {int u,v,l,r;} e[N];

vi simulateCollapse(int _n,vi t,vi x,vi y,vi w,vi p) {
  n=_n, k=t.size(), q=w.size(), b=sqrt(k);
  rep(i,1,k) {
    int op=t[i-1], u=x[i-1]+1, v=y[i-1]+1;
    if(u<v) swap(u,v);
    if(op==0) {
      ++m; ed[pii(u,v)]=pii(m,i);
    } else {  
      auto [id,l]=ed[pii(u,v)]; ed.erase(pii(u,v));
      e[id]=(edge){u,v,l,i-1};
    }
  }
  for(auto [p,q]:ed) {
    int u=p.fi, v=p.se, id=q.fi, l=q.se;
    e[id]=(edge){u,v,l,k};
  }
  for(int l=1,r=b;l<=k;l=r+1) {
    r=min(k,l+b-1); vector<edge> E;
    rep(i,1,n) g[i].clear(), d[i].clear(), f[i].clear();
    rep(i,1,m) {
      if(e[i].l>r||e[i].r<l) continue;
      else if(e[i].l>l||r<e[i].r) E.eb(e[i]);
      else d[e[i].u].eb(e[i].v), f[e[i].v].eb(e[i].u);
    }
    rep(i,1,q) {
      int t=w[i-1]+1, x=p[i-1]+1;
      if(l<=t&&t<=r) g[x].eb(t,i);
    }
    A.init(); B.init(); vi tp;
    rep(i,1,n) {
      A.cnt++; for(int j:d[i]) A.merge(i,j);
      for(auto [t,id]:g[i]) {
        static int vst[N]; tp.clear();
        int res=A.qry();
        for(auto x:E) if(x.l<=t&&t<=x.r&&x.u<=i) {
          int u=A.find(x.u), v=A.find(x.v);
          if(!vst[u]) tp.eb(u), vst[u]=1;
          if(!vst[v]) tp.eb(v), vst[v]=1;
        }
        B.init(tp); res-=tp.size();
        for(auto x:E) if(x.l<=t&&t<=x.r&&x.u<=i) {
          int u=A.find(x.u), v=A.find(x.v);
          B.merge(u,v);
        }
        res+=B.qry(); ans[id]+=res;
      }
    }
    rep(i,1,n) g[i].clear();
    rep(i,1,q) {
      int t=w[i-1]+1, x=p[i-1]+1;
      if(l<=t&&t<=r) g[x+1].eb(t,i);
    }
    A.init(); B.init();
    per(i,n,1) {
      A.cnt++; for(int j:f[i]) A.merge(i,j);
      for(auto [t,id]:g[i]) {
        static int vst[N]; tp.clear();
        int res=A.qry();
        for(auto x:E) if(x.l<=t&&t<=x.r&&x.v>=i) {
          int u=A.find(x.u), v=A.find(x.v);
          if(!vst[u]) tp.eb(u), vst[u]=1;
          if(!vst[v]) tp.eb(v), vst[v]=1;
        }
        B.init(tp); res-=tp.size();
        for(auto x:E) if(x.l<=t&&t<=x.r&&x.v>=i) {
          int u=A.find(x.u), v=A.find(x.v);
          B.merge(u,v);
        }
        res+=B.qry(); ans[id]+=res;
      }
    }
  }
  vi res; rep(i,1,q) res.eb(ans[i]); return res;
}