#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long
int n,m,q;
int p[N];
int r[N];
int dsu(int x){
if(p[x]<0)return x;
return p[x]=dsu(p[x]);
}
bool merge(int x,int y){
x=dsu(x);
y=dsu(y);
if(x==y)return 0;
if(p[x]<p[y])swap(x,y);
p[y]+=p[x];
p[x]=y;
return 1;
}
struct Node {
int x;
Node *l = 0;
Node *r = 0;
Node *p = 0;
bool rev = false;
Node() = default;
Node(int v) { x = v; }
void push() {
if (rev) {
rev = false;
swap(l, r);
if (l) l->rev ^= true;
if (r) r->rev ^= true;
}
}
bool is_root() { return p == 0 || (p->l != this && this != p->r); }
};
struct LCT {
vector<Node> a;
LCT(int n) {
a.resize(n + 1);
for (int i = 1; i <= n; ++i) a[i].x = i;
}
void rot(Node *c) {
auto p = c->p;
auto g = p->p;
if (!p->is_root()) (g->r == p ? g->r : g->l) = c;
p->push();
c->push();
if (p->l == c) { // rtr
p->l = c->r;
c->r = p;
if (p->l) p->l->p = p;
} else { // rtl
p->r = c->l;
c->l = p;
if (p->r) p->r->p = p;
}
p->p = c;
c->p = g;
}
void splay(Node *c) {
while (!c->is_root()) {
auto p = c->p;
auto g = p->p;
if (!p->is_root()) rot((g->r == p) == (p->r == c) ? p : c);
rot(c);
}
c->push();
}
Node *access(int v) {
Node *last = 0;
Node *c = &a[v];
for (Node *p = c; p; p = p->p) {
splay(p);
p->r = last;
last = p;
}
splay(c);
return last;
}
void make_root(int v) {
access(v);
auto *c = &a[v];
if (c->l) c->l->rev ^= true, c->l = 0;
}
void link(int u, int v) {
make_root(v);
Node *c = &a[v];
c->p = &a[u];
}
void cut(int u, int v) {
make_root(u);
access(v);
if (a[v].l) {
a[v].l->p = 0;
a[v].l = 0;
}
}
bool connected(int u, int v) {
access(u);
access(v);
return a[u].p;
}
};
vector<int> simulateCollapse(int _n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) {
n=_n;
m=X.size();
q=W.size();
vector<int>ans(q,0);
if(is_sorted(P.begin(),P.end())){
vector<int>ord;
for(int i=0;i<q;i++){
ord.push_back(i);
}
sort(ord.begin(),ord.end(),[&W](int x,int y){
return W[x]<W[y];
});
int cur=n;
int j=0;
set<pair<int,int>>s;
LCT ln(n);
for(auto i:ord){
while(j<=W[i]){
if(X[j]<=P[i]&&P[i]+1<=Y[j])continue;
if(T[j]==0){
if(!ln.connected(X[j]+1,Y[j]+1)){
cur--;
}
ln.link(X[j]+1,Y[j]+1);
}
else{
ln.cut(X[j]+1,Y[j]+1);
if(!ln.connected(X[j]+1,Y[j]+1)){
cur++;
}
}
j++;
}
ans[i]=cur;
}
return ans;
}
{
map<pair<int,int>,int>s;
for(int i=m-1;i>=0;i--){
if(X[i]>Y[i])swap(X[i],Y[i]);
r[i]=m+1;
if(T[i]==1){
s[{X[i],Y[i]}]=i;
}
else{
r[i]=s[{X[i],Y[i]}];
if(r[i]==0){
r[i]=m+1;
}
}
}
}
for(int i=0;i<q;i++){
ans[i]=n;
for(int j=0;j<n;j++){
p[j]=-1;
}
for(int j=0;j<=W[i];j++){
if(X[j]<=P[i]&&P[i]+1<=Y[j])continue;
if(T[j]==0&&r[j]>W[i]){
if(merge(X[j],Y[j])){
ans[i]--;
}
}
}
}
return ans;
}
