#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
using ll = long long;
const int nx = 100000 + 5;
const int bl = 300;
struct dak {
vector<int> par, sz;
// history as (type, index, old_value)
// type 0 = par[idx] old value, type 1 = sz[idx] old value
vector<tuple<int,int,int>> his;
void init(int n) {
par.resize(n);
sz.assign(n, 1);
for(int i = 0; i < n; ++i) par[i] = i;
his.clear();
}
int find(int u) {
return par[u] == u ? u : par[u] = find(par[u]);
}
bool join(int u, int v) {
u = find(u); v = find(v);
if (u == v) return false;
if (sz[u] < sz[v]) swap(u, v);
his.emplace_back(0, v, par[v]);
his.emplace_back(1, u, sz[u]);
par[v] = u;
sz[u] += sz[v];
return true;
}
int snapshot() { return (int)his.size(); }
void roll(int tmp) {
while ((int)his.size() > tmp) {
auto [type, idx, old] = his.back(); his.pop_back();
if (type == 0) par[idx] = old;
else sz[idx] = old;
}
}
} dsu;
// global buckets (0-based vertex indexing)
static vector<int> f[nx], ve[nx], rev[nx];
static map<ii,int> mp;
vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
int c = (int)t.size();
int q = (int)w.size();
// --- normalize input indexing to 0-based for vertices and positions ---
// heuristic: if any vertex equals n, assume 1-based and subtract 1
bool vertices_one_based = false;
for (int i = 0; i < c; ++i) if (x[i] == n || y[i] == n) { vertices_one_based = true; break; }
if (vertices_one_based) {
for (int i = 0; i < c; ++i) { x[i]--; y[i]--; }
}
bool pos_one_based = false;
for (int i = 0; i < q; ++i) if (p[i] == n) { pos_one_based = true; break; }
if (pos_one_based) for (int i = 0; i < q; ++i) p[i]--;
vector<int> del(c, c), ans(q, 0), id(q), out;
mp.clear();
for (int i = 0; i < c; ++i) {
if (x[i] > y[i]) swap(x[i], y[i]);
if (t[i]) {
// delete operation: matching add should exist
auto it = mp.find({x[i], y[i]});
if (it != mp.end()) del[it->second] = i;
else {
// unmatched delete: ignore or set to i (defensive)
}
} else {
mp[{x[i], y[i]}] = i;
}
}
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int aa, int bb){ return w[aa] < w[bb]; });
int l = 0, poi = 0;
while (l < c) {
int r = min(l + bl, c - 1);
// clear buckets
for (int i = 0; i < n; ++i) {
f[i].clear(); ve[i].clear(); rev[i].clear();
}
out.clear();
// prepare queries whose w <= r
while (poi < q && w[id[poi]] <= r) {
if (p[id[poi]] >= 0 && p[id[poi]] < n) f[p[id[poi]]].push_back(id[poi]);
else {
// defensive: ignore out-of-range p
}
++poi;
}
// classify edges whose add time < l
for (int i = 0; i < l; ++i) {
if (t[i]) continue; // skip deletes
if (del[i] >= l) {
if (del[i] > r) {
// alive through this block, but removed later -> used in sweep
ve[y[i]].push_back(i);
rev[x[i]].push_back(i);
} else {
// deleted within block: treat as exceptional
out.push_back(i);
}
}
}
// forward sweep
int cc = 0;
dsu.init(n);
for (int i = 0; i < n; ++i) {
++cc;
for (int idx : ve[i]) if (dsu.join(x[idx], y[idx])) --cc;
for (int idx : f[i]) {
int tmp = dsu.snapshot();
int cnt = 0;
for (int j : out) if (y[j] <= i && del[j] > w[idx]) {
if (dsu.join(x[j], y[j])) { --cc; ++cnt; }
}
for (int j = l; j <= w[idx]; ++j) {
if (t[j] == 0 && y[j] <= i && del[j] > w[idx]) {
if (dsu.join(x[j], y[j])) { --cc; ++cnt; }
}
}
ans[idx] += cc;
cc += cnt;
dsu.roll(tmp);
}
}
// backward sweep
cc = 0;
dsu.init(n);
for (int i = n - 1; i >= 1; --i) {
++cc;
for (int idx : rev[i]) if (dsu.join(x[idx], y[idx])) --cc;
for (int idx : f[i-1]) {
int tmp = dsu.snapshot();
int cnt = 0;
for (int j : out) if (x[j] >= i && del[j] > w[idx]) {
if (dsu.join(x[j], y[j])) { --cc; ++cnt; }
}
for (int j = l; j <= w[idx]; ++j) {
if (t[j] == 0 && x[j] >= i && del[j] > w[idx]) {
if (dsu.join(x[j], y[j])) { --cc; ++cnt; }
}
}
ans[idx] += cc;
cc += cnt;
dsu.roll(tmp);
}
}
l = r + 1;
}
return ans;
}
// Note: main() intentionally omitted (library function)
