#include "collapse.h"
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <iostream>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())
const int bs = 250;
vi simulateCollapse(int N, vi T, vi X, vi Y, vi W, vi P)
{
int C = sz(T);
int Q = sz(W);
for(int i = 0; i < C; i++)
{
if(X[i] > Y[i])
swap(X[i], Y[i]);
}
vi res(Q);
for(int q = 0; q < Q; q++)
{
set<pii> edges;
for(int i = 0; i <= W[q]; i++)
{
if(X[i] <= P[q] && P[q]+1 <= Y[i]) continue;
if(T[i] == 0)
edges.insert({X[i], Y[i]});
else
edges.erase({X[i], Y[i]});
}
vi edge[N];
for(auto& z : edges)
{
edge[z.first].push_back(z.second);
edge[z.second].push_back(z.first);
}
int comps = 0;
vi vis(N, 0);
queue<int> tbv;
for(int i = 0; i < N; i++)
{
if(vis[i]) continue;
comps++;
vis[i] = 1;
tbv.push(i);
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
for(int v : edge[u])
{
if(vis[v]) continue;
tbv.push(v);
vis[v] = 1;
}
}
}
res[q] = comps;
// cout << comps << '\n';
}
return res;
}
