#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
template<class T, size_t D>
ostream &operator << (ostream &os, array<T, D> u) {
os << "{";
for (size_t i = 0; i < D; ++i) {
os << (i ? ", " : "") << u[i];
}
return os << "}";
}
template<class T>
ostream &operator << (ostream &os, vector<T> u) {
os << "{";
for (int i = 0; i < u.size(); ++i) {
os << (i ? ", " : "") << u[i];
}
return os << "}";
}
void __print() {
cerr << "]\n";
}
template<class T, class... V>
void __print(T t, V... v) {
cerr << t;
if (sizeof...(v)) {
cerr << ", ";
}
__print(v...);
}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; __print(x);
#else
#define debug(...) 42
#endif
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
const int S = 320;
int C = X.size(), Q = W.size();
int cnt = 0;
vector<int> lab(N, -1);
vector<array<int, 2>> his;
auto init = [&]() {
fill(lab.begin(), lab.end(), -1);
cnt = 0;
};
auto find = [&](int u) -> int {
while (lab[u] >= 0) {
u = lab[u];
}
return u;
};
auto unite = [&](int u, int v, bool keep) {
u = find(u), v = find(v);
if (u == v) {
if (keep) {
his.push_back({-1, -1});
}
return;
}
if (lab[u] > lab[v]) {
swap(u, v);
}
if (keep) {
his.push_back({v, lab[v]});
}
++cnt;
lab[u] += lab[v];
lab[v] = u;
};
auto restore = [&]() {
while (his.size()) {
auto e = his.back(); his.pop_back();
if (~e[0]) {
--cnt;
int &p = lab[e[0]];
lab[p] -= e[1];
p = e[1];
}
}
};
vector<array<int, 2>> comp;
for (int i = 0; i < C; ++i) {
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
comp.push_back({X[i], Y[i]});
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
int M = comp.size();
vector<int> pos(C);
for (int i = 0; i < C; ++i) {
T[i] ^= 1;
pos[i] = lower_bound(comp.begin(), comp.end(), array<int, 2>{X[i], Y[i]}) - comp.begin();
}
vector<array<int, 3>> queries;
vector<int> res(Q);
for (int i = 0; i < Q; ++i) {
queries.push_back({P[i], W[i], i});
res[i] = N;
}
sort(queries.begin(), queries.end(), [&](const auto &u, const auto &v) {
return u[1] < v[1];
});
vector<bool> tog(M), cur(M), nw(M);
int ptr = 0;
for (int i = 0; i < C; i += S) {
int l = i, r = min(C - 1, i + S - 1);
for (int j = l; j <= r; ++j) {
tog[pos[j]] = 1;
}
vector<int> add;
vector<array<int, 2>> cands;
for (int j = 0; j < M; ++j) {
if (!tog[j] && cur[j]) {
cands.push_back(comp[j]);
}
if (tog[j]) {
add.push_back(j);
}
}
vector<array<int, 3>> ord;
while (ptr < Q && queries[ptr][1] <= r) {
ord.push_back(queries[ptr++]);
}
sort(ord.begin(), ord.end());
sort(cands.begin(), cands.end(), [&](const auto &u, const auto &v) {
return u[1] < v[1];
});
init();
int k = 0;
for (auto [x, d, id] : ord) {
while (k < cands.size() && cands[k][1] <= x) {
unite(cands[k][0], cands[k][1], 0);
++k;
}
for (int j = l; j <= d; ++j) {
nw[pos[j]] = T[j];
}
for (int id : add) {
if (nw[id] && comp[id][1] <= x) {
unite(comp[id][0], comp[id][1], 1);
}
nw[id] = cur[id];
}
res[id] -= cnt;
restore();
}
init();
reverse(ord.begin(), ord.end());
sort(cands.rbegin(), cands.rend());
k = 0;
for (auto [x, d, id] : ord) {
while (k < cands.size() && cands[k][0] > x) {
unite(cands[k][0], cands[k][1], 0);
++k;
}
for (int j = l; j <= d; ++j) {
nw[pos[j]] = T[j];
}
for (int id : add) {
if (nw[id] && comp[id][0] > x) {
unite(comp[id][0], comp[id][1], 1);
}
nw[id] = cur[id];
}
res[id] -= cnt;
restore();
}
for (int j = l; j <= r; ++j) {
tog[pos[j]] = 0;
cur[pos[j]] = T[j];
nw[pos[j]] = cur[pos[j]];
}
}
return res;
}
