#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
// #define LOCAL
#ifdef LOCAL
#else
#include "collapse.h"
#endif
const int BLOCK = 1000;
int N;
template<int SZ> struct realDSU {
int par[SZ], numComp = 0;
void init(int co) {
F0R(i,co) par[i] = i;
}
int get(int x) { // path compression
if (par[x] != x) par[x] = get(par[x]);
return par[x];
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return 0;
if (rand()&1) swap(x,y);
par[y] = x; numComp --;
return 1;
}
};
struct DSU { // persistent DSU
vpi par[MX], child[MX];
int numComp[MX];
DSU() {
F0R(i,N) {
par[i].pb({-1,i});
child[i].pb({-1,i});
}
}
int getComp(int ti) { return numComp[ti]; }
int get(int ti, int x) { return prev(ub(all(par[x]),mp(ti,MOD)))->s; }
void unite(int ti, int x, int y) {
x = par[x].back().s, y = par[y].back().s;
if (x == y) return;
numComp[ti] --;
if (sz(child[x]) < sz(child[y])) swap(x,y);
for (auto a: child[y]) {
par[a.s].pb({ti,x});
child[x].pb({ti,a.s});
}
}
};
vi ans;
vector<array<int,3>> change;
vpi tri[MX];
unordered_set<int> from[MX], to[MX];
set<pi> tedge;
int m[MX];
realDSU<2*BLOCK> R;
int mini(const vpi& v) {
int co = 0;
for (auto a: v) m[a.f] = m[a.s] = -1;
for (auto a: v) {
if (m[a.f] == -1) m[a.f] = co ++;
if (m[a.s] == -1) m[a.s] = co ++;
}
R.init(co);
int res = 0;
for (auto a: v)
if (R.unite(m[a.f],m[a.s])) res ++;
return res;
}
vector<pair<pi,set<pi>>> todo;
void solveA() {
realDSU<MX> A = realDSU<MX>();
A.init(N);
int ind = 0;
F0R(i,N) {
A.numComp ++;
for (int x: to[i]) A.unite(x,i);
while (ind < sz(todo) && todo[ind].f.f == i) {
ans[todo[ind].f.s] += A.numComp;
vpi tmp;
for (auto z: todo[ind].s) if (z.s <= i)
tmp.pb({A.get(z.f),A.get(z.s)});
ans[todo[ind].f.s] -= mini(tmp);
ind ++;
}
}
}
void solveB() {
realDSU<MX> B = realDSU<MX>();
B.init(N);
int ind = 0;
F0R(i,N) {
B.numComp ++;
for (int x: from[N-1-i]) B.unite(x,N-1-i);
while (ind < sz(todo) && todo[ind].f.f+1 == N-1-i) {
ans[todo[ind].f.s] += B.numComp;
vpi tmp;
for (auto z: todo[ind].s) if (z.f >= N-1-i)
tmp.pb({B.get(z.f),B.get(z.s)});
ans[todo[ind].f.s] -= mini(tmp);
ind ++;
}
}
}
void genDSU() {
sort(all(todo));
solveA();
reverse(all(todo));
solveB();
todo.clear();
}
void process(int l, int r) {
FOR(i,l,r+1) {
pi cur = {change[i][1],change[i][2]};
if (from[cur.f].count(cur.s)) {
from[cur.f].erase(cur.s); to[cur.s].erase(cur.f);
tedge.insert(cur);
}
}
FOR(i,l,r+1) {
pi cur = {change[i][1],change[i][2]};
if (change[i][0] == 0) tedge.insert(cur);
else tedge.erase(cur);
for (auto a: tri[i]) todo.pb({a,tedge});
}
genDSU();
for (auto a: tedge) from[a.f].insert(a.s), to[a.s].insert(a.f);
tedge.clear();
}
vi simulateCollapse(int n, vi T, vi X, vi Y, vi W, vi P) {
N = n;
F0R(i,sz(X)) {
if (X[i] > Y[i]) swap(X[i],Y[i]);
change.pb({T[i],X[i],Y[i]});
}
ans.resize(sz(W));
F0R(i,sz(ans)) tri[W[i]].pb({P[i],i});
for (int i = 0; i < sz(X); i += BLOCK) process(i,min(i+BLOCK,sz(X))-1);
return ans;
}
#ifdef LOCAL
int main(int argc, char *argv[]) {
int N, C, Q;
//cin >> N;
//C = Q = N;
scanf("%d%d%d", &N, &C, &Q);
std::vector<int> T(C), X(C), Y(C);
for(int i = 0; i < C; i++) {
// T[i] = 0; X[i] = rand() % N, Y[i] = rand() % N;
scanf("%d%d%d", &T[i], &X[i], &Y[i]);
}
std::vector<int> W(Q), P(Q);
for(int i = 0; i < Q; i++) {
// W[i] = rand() % N; P[i] = rand() % (N-1);
scanf("%d%d", &W[i], &P[i]);
}
auto res = simulateCollapse(N, T, X, Y, W, P);
printf("%d\n",Q);
for(auto i : res) {
printf("%d\n", i);
}
}
/*
5 8 2
0 0 1
0 1 3
0 2 4
0 4 0
1 1 3
0 0 3
0 1 2
0 4 3
3 1
7 3
*/
#endif
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
