#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
vector<int> par;
vector<int> par2;
vector<int> last;
int tt;
int find(int u) {
if (par[u] == u) {
return u;
} else {
return par[u] = find(par[u]);
}
}
bool merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) {
return false;
} else {
par[v] = u;
return true;
}
}
int find2(int u) {
if (last[u] != tt) {
last[u] = tt;
par2[u] = par[u];
}
if (par2[u] == u) {
return u;
} else {
return par2[u] = find2(par2[u]);
}
}
bool merge2(int u, int v) {
u = find2(u);
v = find2(v);
if (u == v) {
return false;
} else {
par2[v] = u;
return true;
}
}
vector<int> simulateCollapse(int n, vector<int> type, vector<int> from, vector<int> to, vector<int> time, vector<int> pos) {
int m = type.size();
int q = time.size();
par.resize(n);
par2.resize(n);
last.assign(n, 0);
for (int i = 0; i < m; ++i) {
if (from[i] > to[i]) {
swap(from[i], to[i]);
}
}
vector<int> go(m);
{
map<pair<int, int>, int> st;
for (int i = 0; i < m; ++i) {
pair<int, int> e = make_pair(from[i], to[i]);
if (type[i] == 0) {
st[e] = i;
} else {
assert(st.count(e));
go[st[e]] = i;
st.erase(e);
}
}
for (auto p : st) {
go[p.second] = m;
}
}
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
int ncomp = n;
for (int j = 0; j < n; ++j) {
par[j] = j;
}
for (int j = 0; j < m; ++j) {
if (type[j] == 0 && j <= time[i] && time[i] < go[j]) {
if (to[j] <= pos[i] || from[j] > pos[i]) {
ncomp -= merge(from[j], to[j]);
}
}
}
ans[i] = ncomp;
}
return ans;
}
