#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> brute(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
int m = (int)t.size();
int q = (int)w.size();
for (int i = 0; i < m; i++) {
if (x[i] > y[i]) {
swap(x[i], y[i]);
assert(0 <= x[i] && x[i] < y[i] && y[i] < n);
}
}
assert((int) t.size() == m);
assert((int) x.size() == m);
assert((int) y.size() == m);
assert((int) w.size() == q);
assert((int) p.size() == q);
vector<int> sol((int) w.size());
for (int iq = 0; iq < (int) w.size(); iq++) {
set<pair<int, int>> s;
for (int i = 0; i <= w[iq]; i++) {
pair<int, int> cur = make_pair(x[i], y[i]);
if (s.count(cur)) {
s.erase(cur);
} else {
s.insert(cur);
}
}
vector<pair<int, int>> ve;
for (auto &it : s) {
if (it.first <= p[iq] && it.second > p[iq]) {
continue;
}
ve.push_back(it);
}
vector<int> t(n);
iota(t.begin(), t.end(), 0);
int comps = n;
function<int(int)> getpap = [&] (int a) {
if (t[a] == a) {
return a;
} else {
return t[a] = getpap(t[a]);
}
};
function<void(int, int)> unite = [&] (int a, int b) {
a = getpap(a);
b = getpap(b);
if (a != b) {
comps--;
t[a] = b;
}
};
for (auto &it : ve) {
unite(it.first, it.second);
}
sol[iq] = comps;
}
return sol;
}
//const int edgeM = 333;
const int edgeM = 7;
vector<int> smart(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
int m = (int)t.size();
int q = (int)w.size();
for (int i = 0; i < m; i++) {
if (x[i] > y[i]) {
swap(x[i], y[i]);
assert(0 <= x[i] && x[i] < y[i] && y[i] < n);
}
}
assert((int) t.size() == m);
assert((int) x.size() == m);
assert((int) y.size() == m);
assert((int) w.size() == q);
assert((int) p.size() == q);
vector<int> sol((int) w.size());
for (int ISTEP = 1; ISTEP <= 2; ISTEP++) {
vector<int> edgeBucket(m), edgeFirst(m), edgeLast(m);
for (int i = 0; i < m; i++) {
edgeBucket[i] = i / edgeM;
edgeLast[edgeBucket[i]] = i;
}
for (int i = m - 1; i >= 0; i--) {
edgeFirst[edgeBucket[i]] = i;
}
vector<vector<int>> inds(m);
for (int i = 0; i < q; i++) {
inds[w[i]].push_back(i);
}
set<pair<int, int>> s;
for (int edgeBucketId = edgeBucket[0]; edgeBucketId <= edgeBucket[m - 1]; edgeBucketId++) {
for (int step = edgeFirst[edgeBucketId]; step <= edgeLast[edgeBucketId]; step++) {
pair<int, int> cur = make_pair(x[step], y[step]);
if (s.count(cur)) {
s.erase(cur);
} else {
s.insert(cur);
}
for (auto &iq : inds[step]) {
vector<pair<int, int>> ve;
for (auto &it : s) {
if (it.second <= p[iq]) {
ve.push_back(it);
continue;
}
}
vector<int> t(n);
iota(t.begin(), t.end(), 0);
int comps = p[iq] + 1;
function<int(int)> getpap = [&] (int a) {
if (t[a] == a) {
return a;
} else {
return t[a] = getpap(t[a]);
}
};
function<void(int, int)> unite = [&] (int a, int b) {
a = getpap(a);
b = getpap(b);
if (a != b) {
comps--;
t[a] = b;
}
};
for (auto &it : ve) {
unite(it.first, it.second);
}
sol[iq] += comps;
}
}
}
for (int i = 0; i < m; i++) {
swap(x[i], y[i]);
x[i] = n - 1 - x[i];
y[i] = n - 1 - y[i];
}
for (int i = 0; i < q; i++) {
p[i] = n - 2 - p[i];
}
}
return sol;
}
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
auto B=brute(N,T,X,Y,W,P);
auto S=smart(N,T,X,Y,W,P);
assert(B==S);
return S;
}
