// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class T>
bool minimize(T &a, const T &b) {
if (a > b) return a = b, true;
return false;
}
template<class T>
bool maximize(T &a, const T &b) {
if (a < b) return a = b, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"
const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 1e5 + 5;
const int S = 500;
int n, q, c;
struct DSU {
vector<int> lab;
vector<array<int, 4>> history;
int connected;
DSU(int n = 0): lab(n, -1), connected(0) {}
int root(int v) {
return (lab[v] < 0 ? v : root(lab[v]));
}
bool unite(int u, int v) {
u = root(u); v = root(v);
if (u == v) return false;
if (lab[u] > lab[v]) swap(u, v);
history.pb({u, v, lab[u], lab[v]});
connected++;
lab[u] += lab[v];
lab[v] = u;
return true;
}
void roll_back() {
while(!history.empty()) {
auto tmp = history.back(); history.pop_back();
lab[tmp[0]] = tmp[2];
lab[tmp[1]] = tmp[3];
connected--;
}
}
} dsu;
vector<ii> event[N];
vector<int> up[N], down[N], upB[N], downB[N];
vector<int> queries[N];
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
n = N;
c = T.size();
q = W.size();
REP(i, c) if (X[i] > Y[i])
swap(X[i], Y[i]);
vector<int> query;
REP(i, q) query.pb(i);
sort(all(query), [&](int &x, int &y){
return W[x] < W[y];
});
vector<int> res(q, 0);
vector<bool> is_del(c, false);
vector<int> index(c, c);
map<ii, int> id;
REP(i, c) {
if (T[i] == 0) {
id[{X[i], Y[i]}] = i;
} else index[i] = id[{X[i], Y[i]}];
}
int Q = 0;
for(int B = 0; B < c; B += S) {
int L = B, R = min(c, B + S) - 1;
int _Q = Q;
for(; _Q < q && W[query[_Q]] <= R; _Q++) {
int i_q = query[_Q];
queries[P[i_q]].pb(i_q);
}
vector<bool> up_check(n, false), down_check(n, false);
vector<int> ups, downs;
vector<int> edges_out;
FOR(i, L, R) {
if (T[i] == 0) {
if (up_check[Y[i]] == false) {
ups.pb(Y[i]);
up_check[Y[i]] = true;
}
if (down_check[X[i]] == false) {
downs.pb(X[i]);
down_check[X[i]] = true;
}
upB[Y[i]].pb(i);
downB[X[i]].pb(i);
} else {
if (index[i] < L) edges_out.pb(i), is_del[index[i]] = true;
}
}
sort(all(ups));
sort(all(downs), greater<int>());
// answer query up
dsu = DSU(n);
REP(w, n) {
for(int &i : up[w]) if (!is_del[i])
dsu.unite(X[i], Y[i]);
dsu.history.clear();
for(int &i_q : queries[w]) {
FOR(i, L, W[i_q]) if (T[i] == 1) {
is_del[index[i]] = true;
}
for(int &i_del : edges_out) {
if (i_del > W[i_q]) break;
int id_edge = index[i_del];
if (Y[id_edge] <= w) dsu.unite(X[id_edge], Y[id_edge]);
}
for(int &i : ups) {
if (i > w) break;
for(int &j : upB[i]) if (j <= W[i_q] && !is_del[j])
dsu.unite(X[j], Y[j]);
}
res[i_q] += w + 1 - dsu.connected; // scc with index <= p
dsu.roll_back();
FOR(i, L, W[i_q]) if (T[i] == 1 && L <= index[i]) {
is_del[index[i]] = false;
}
}
}
// answer query down
dsu = DSU(n);
RED(w, n) {
for(int &i_q : queries[w]) {
FOR(i, L, W[i_q]) if (T[i] == 1) {
is_del[index[i]] = true;
}
for(int &i_del : edges_out) {
if (i_del > W[i_q]) break;
int id_edge = index[i_del];
if (X[id_edge] > P[i_q]) dsu.unite(X[id_edge], Y[id_edge]);
}
for(int &i : downs) {
if (i <= w) break;
for(int &j : downB[i]) if (j <= W[i_q] && !is_del[j])
dsu.unite(X[j], Y[j]);
}
res[i_q] += n - (w + 1) - dsu.connected;
dsu.roll_back();
FOR(i, L, W[i_q]) if (T[i] == 1 && L <= index[i]) {
is_del[index[i]] = false;
}
}
for(int &i : down[w]) if (!is_del[i])
dsu.unite(X[i], Y[i]);
dsu.history.clear();
}
// clear query + add edge in current block
for(; Q < _Q; Q++) {
int i_q = query[Q];
queries[P[i_q]].clear();
}
FOR(i, L, R) if (T[i] == 1)
is_del[index[i]] = true;
FOR(i, L, R) {
if (!is_del[i] && T[i] == 0) {
up[Y[i]].pb(i);
down[X[i]].pb(i);
}
upB[Y[i]].clear();
downB[X[i]].clear();
}
}
return res;
}
// int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// auto ans = simulateCollapse(5, {0, 1, 0, 0, 0, 1, 0}, {1, 3, 1, 0, 1, 0, 4}, {3, 1, 2, 2, 0, 1, 1},
// {2, 2, 2, 2, 2}, {0, 1, 2, 3, 4});
// for(int x : ans) cout << x << ' '; cout << '\n';
// return 0;
// }
