#include "collapse.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 998244353 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b) % mo;
}
const int maxn = 1e5+5;
const int BS = 800;
int state[maxn];
int ndel = 0; // Number of things that are connected
int ans[maxn], sz[maxn];
int par[maxn];
vector<int> stk;
int find(int x){
return x == par[x]?x:find(par[x]);
}
void setup(){
ndel = 0;
stk.clear();
for (int i = 0; i<maxn; ++i) par[i] = i, sz[i] = 1;
}
inline void undo(){
if (!stk.empty()) {
--ndel;
sz[par[stk.back()]] -= sz[stk.back()];
par[stk.back()] = stk.back();
stk.pop_back();
}
}
inline bool merge(int a, int b) {
a = find(a); b = find(b);
if (a == b) return 0;
++ndel;
if (sz[a] < sz[b]) {
swap(a,b);
}
stk.pb(b);
sz[a] += sz[b];
par[b] = a;
return 1;
}
vector<pii > g[maxn]; // to, time
vector<pii> quat[maxn]; // For this position, what time do I query and what id is it?
int itof[maxn];
int ID[maxn];
bool notsure[maxn];
void go(int n,vector<int> TP,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) {
// TP: query type, 0 is add, 1 is delete
// X,Y: Edge endpoints
// W: Query time
// P: Query position
// n: Length of the country
memset(itof, 0, sizeof itof);
int m = SZ(X), q = SZ(W);
// SQRT by Time
for (int t = 0; t<m; t += BS) {
int t2 = min(m, t+BS);
for (int i = t; i<t2; ++i) {
notsure[ID[i]] = 1;
}
setup();
for (int i = 0; i<n; ++i) {
for (pii x : g[i]) {
if (!notsure[x.s] && state[x.s]) {
merge(x.f,i);
}
}
while (itof[i] < SZ(quat[i]) && quat[i][itof[i]] .f < t2) {
int T = quat[i][itof[i]] .f, ansit = quat[i][itof[i]].s;
assert(T >= t && T < t2);
int nund = 0; // number of necessary undoes
for (int j = t; j<=T; ++j) {
state[ID[j]]^=1;
}
for (int j = t; j<t2; ++j) {
if (Y[j] <=i && state[ID[j]]) {
nund += merge(X[j], Y[j]);
}
}
for (int j = t; j<=T; ++j) {
state[ID[j]]^=1;
}
ans[ansit] += ndel;
++itof[i];
for (int cnt = 0; cnt < nund; ++cnt) undo();
}
}
for (int i = t; i<t2; ++i) {
state[ID[i]]^=1;
notsure[ID[i]] = 0;
}
}
}
vector<int> simulateCollapse(int n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P){
int q = SZ(P);
vector<pii> all;
for (int i = 0; i<SZ(X); ++i) {
if (X[i] > Y[i]) swap(X[i], Y[i]);
all.pb({X[i], Y[i]});
}
SORT_UNIQUE(all);
for (int i = 0; i<SZ(X); ++i) {
ID[i] = lower_bound(ALL(all), make_pair(X[i], Y[i])) - all.begin();
}
{
set<pii> tmp;
for (int i = 0; i<SZ(X); ++i) {
if (X[i] > Y[i]) swap(X[i], Y[i]);
if (!tmp.count({X[i], Y[i]})) {
g[Y[i]].pb({X[i], ID[i]});
tmp.insert({X[i], Y[i]});
}
}
for (int i = 0; i<SZ(P); ++i) {
quat[P[i]] .pb ({W[i], i});
}
for (int i = 0; i<n; ++i) {
sort(ALL(quat[i]));
}
go(n,T,X,Y,W,P);
}
for (int i = 0; i<q; ++i) bug(i,ans[i]);
for(int i = 0; i<n; ++i) g[i].clear(), quat[i].clear();
memset(state, 0, sizeof state);
for (int i = 0; i<SZ(X); ++i) {
X[i] = n-X[i] - 1;
Y[i] = n-Y[i] - 1;
}
for (int i = 0; i<SZ(P); ++i) {
P[i] = n-P[i] - 2;
}
{
set<pii> tmp;
for (int i = 0; i<SZ(X); ++i) {
if (X[i] > Y[i]) swap(X[i], Y[i]);
if (!tmp.count({X[i], Y[i]})) {
g[Y[i]].pb({X[i],ID[i]});
tmp.insert({X[i], Y[i]});
}
}
for (int i = 0; i<SZ(P); ++i) {
quat[P[i]] .pb ({W[i], i});
}
for (int i = 0; i<n; ++i) {
sort(ALL(quat[i]));
}
go(n,T,X,Y,W,P);
}
vector<int> re(q);
for (int i = 0; i<q; ++i) {
bug(i, ans[i]);
re[i] = n-ans[i];
}
return re;
}
#ifdef BALBITe
signed main(){
IOS();
simulateCollapse(5,)
}
#endif
/*
4 4 9
0 0 2
0 1 3
0 2 3
1 2 3
1 0
1 1
1 2
2 0
2 1
2 2
3 0
3 1
3 2
*/
