#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Event {
int T, type, x, y;
bool operator < (const Event& rhs) const {
return (T == rhs.T) ? type < rhs.type : T < rhs.T;
}
};
struct Edge {
int id, u, v;
bool operator < (const Edge& rhs) const {
return u < rhs.u;
}
};
int n;
int par[N];
int res[N];
int f[2][N];
int pos[N];
bool state[N];
bool iedge[N];
bool inode[N];
vector<Event> vec, buf;
vector< pair<int, int> > dsu[2][500];
map< pair<int, int>, int > label;
vector<Edge> E1, E2;
int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }
bool join(int u, int v) {
u = find(u), v = find(v);
if (inode[u]) swap(u, v); // root prefer important node
par[u] = v; return u != v;
}
void solve() {
vector<int> vnode;
vector<Edge> vedge;
int cnt = 0;
for (auto i : buf) {
if (i.type < 0) {
int id = label[{i.x, i.y}];
if (!iedge[id]) {
iedge[id] = 1;
vedge.push_back({id, i.x, i.y});
}
if (!inode[i.x]) {
inode[i.x] = 1, vnode.push_back(i.x);
}
if (!inode[i.y]) {
inode[i.y] = 1, vnode.push_back(i.y);
}
}
else pos[i.type] = cnt++;
}
{
vector< pair<int, int> > vec1;
for (auto i : buf) {
if (i.type >= 0) vec1.push_back({i.x, i.type});
}
sort(vec1.begin(), vec1.end());
for (int i = 0; i < n; ++i) par[i] = i;
int ptr = 0, cur = 0, cnt = 0;
for (auto i : vec1) {
while (cur < i.first) ++cur, ++cnt;
while (ptr < E1.size() && E1[ptr].u <= i.first) {
if (!iedge[E1[ptr].id] && state[E1[ptr].id]) {
cnt -= join(E1[ptr].u, E1[ptr].v);
}
++ptr;
}
f[0][i.second] = cnt;
for (auto j : vnode) {
dsu[0][pos[i.second]].push_back({j, find(j)});
}
}
}
{
vector< pair<int, int> > vec2;
for (auto i : buf) {
if (i.type >= 0) vec2.push_back({i.x + 1, i.type});
}
sort(vec2.begin(), vec2.end());
reverse(vec2.begin(), vec2.end());
for (int i = 0; i < n; ++i) par[i] = i;
int ptr = 0, cur = 0, cnt = 0;
for (auto i : vec2) {
while (cur < n - i.first + 1) ++cur, ++cnt;
while (ptr < E2.size() && E2[ptr].u >= i.first) {
if (!iedge[E2[ptr].id] && state[E2[ptr].id]) {
cnt -= join(E2[ptr].u, E2[ptr].v);
}
++ptr;
}
f[1][i.second] = cnt;
for (auto j : vnode) {
dsu[1][pos[i.second]].push_back({j, find(j)});
}
}
}
for (auto i : buf) {
if (i.type < 0) {
int id = label[{i.x, i.y}];
state[id] ^= 1; continue;
}
int id = i.type;
for (int j = 0; j < 2; ++j) {
for (auto k : dsu[j][pos[id]]) par[k.first] = k.second;
for (auto k : vnode) {
if (j == 0 && k > i.x || j == 1 && k <= i.x) continue;
f[j][id] -= par[k] == k;
}
for (auto k : vedge) {
// k.u < k.v
if (state[k.id] && (k.v <= i.x || k.u > i.x)) join(k.u, k.v);
}
for (auto k : vnode) {
if (j == 0 && k > i.x || j == 1 && k <= i.x) continue;
f[j][id] += par[k] == k;
}
}
res[id] = f[0][id] + f[1][id];
}
for (int i = 0; i < cnt; ++i) dsu[0][i].clear(), dsu[1][i].clear();
for (auto i : buf) {
if (i.type < 0) {
iedge[label[{i.x, i.y}]] = inode[i.x] = inode[i.y] = 0;
}
}
buf.clear();
}
vector<int> simulateCollapse(
int _n,
vector<int> T,
vector<int> X,
vector<int> Y,
vector<int> W,
vector<int> P
) {
n = _n;
int c = T.size();
int q = W.size();
for (int i = 0; i < c; ++i) {
if (X[i] > Y[i]) swap(X[i], Y[i]);
vec.push_back({i, -(T[i] + 1), X[i], Y[i]});
}
for (int i = 0; i < q; ++i) {
vec.push_back({W[i], i, P[i], 0});
}
sort(vec.begin(), vec.end());
int cnt = 0;
for (int i = 0; i < c; ++i) {
if (label[{X[i], Y[i]}]) continue;
label[{X[i], Y[i]}] = ++cnt;
E1.push_back({cnt, Y[i], X[i]});
E2.push_back({cnt, X[i], Y[i]});
}
sort(E1.begin(), E1.end());
sort(E2.begin(), E2.end());
reverse(E2.begin(), E2.end());
for (int i = 0; i < vec.size(); ++i) {
buf.push_back(vec[i]);
if (buf.size() == 365) solve();
}
if (buf.size()) solve();
vector<int> vres;
for (int i = 0; i < q; ++i) vres.push_back(res[i]);
return vres;
}
