#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif
const int S = 320;
vector<int> simulateCollapse(int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
int Q = int(W.size()), C = int(X.size());
vector<int> ord(Q), res(Q);
vector<pair<int, int>> edges;
for (int i = 0; i < C; ++i) {
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
edges.emplace_back(X[i], Y[i]);
}
sort(edges.begin(), edges.end());
edges.erase(unique(edges.begin(), edges.end()), edges.end());
int m = int(edges.size());
vector<int> idx(C);
for (int i = 0; i < C; ++i) {
idx[i] = lower_bound(edges.begin(), edges.end(), make_pair(X[i], Y[i])) - edges.begin();
}
vector<vector<int>> qry(C);
for (int i = 0; i < Q; ++i) {
qry[W[i]].emplace_back(i);
}
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return W[i] < W[j];
});
vector<int> lab(n, -1);
vector<pair<int, int>> his;
int cc = n;
auto get = [&](auto get, int u) -> int {
return lab[u] < 0 ? u : get(get, lab[u]);
};
auto unite = [&](int u, int v, bool rb) {
u = get(get, u), v = get(get, v);
if (u ^ v) {
if (lab[u] > lab[v]) {
swap(u, v);
}
if (rb) {
his.emplace_back(v, lab[v]);
}
lab[u] += lab[v];
lab[v] = u;
cc--;
}
};
auto rollback = [&]() {
while (his.size()) {
auto [v, sz] = his.back();
his.pop_back();
int u = lab[v];
lab[u] -= sz;
lab[v] = sz;
cc++;
}
};
auto reset = [&]() {
cc = n;
fill(lab.begin(), lab.end(), -1);
his.clear();
};
vector<int> inc(m);
iota(inc.begin(), inc.end(), 0);
auto dec = inc;
sort(inc.begin(), inc.end(), [&](int i, int j) {
return edges[i].second < edges[j].second;
});
sort(dec.begin(), dec.end(), [&](int i, int j) {
return edges[i].first > edges[j].first;
});
vector<bool> cant(m, false), state(m, false);
vector<vector<int>> gL(Q), gR(Q);
int time = 0;
for (int s = 0; s < C; s += S) {
int l = s, r = min(C, s + S) - 1;
vector<int> cands;
for (int i = l; i <= r; ++i) {
cands.emplace_back(idx[i]);
}
sort(cands.begin(), cands.end());
cands.erase(unique(cands.begin(), cands.end()), cands.end());
for (int id : cands) {
cant[id] = true;
}
vector<int> v;
for (int i = l; i <= r; ++i) {
state[idx[i]] = 1 - state[idx[i]];
for (int id : qry[i]) {
v.emplace_back(id);
for (int u : cands) {
if (state[u]) {
if (edges[u].second <= P[id]) {
gL[id].emplace_back(u);
} else if (edges[u].first > P[id]) {
gR[id].emplace_back(u);
}
}
}
}
}
sort(v.begin(), v.end(), [&](int i, int j) {
return P[i] < P[j];
});
reset();
int j = 0;
for (int id : v) {
while (j < m && edges[inc[j]].second <= P[id]) {
int i = inc[j];
if (!cant[i] && state[i]) {
unite(edges[i].first, edges[i].second, false);
}
j++;
}
for (int k : gL[id]) {
unite(edges[k].first, edges[k].second, true);
}
res[id] += cc - n + P[id] + 1;
rollback();
}
reverse(v.begin(), v.end());
reset();
j = 0;
for (int id : v) {
while (j < m && edges[dec[j]].first > P[id]) {
int i = dec[j];
if (!cant[i] && state[i]) {
unite(edges[i].first, edges[i].second, false);
}
j++;
}
for (int k : gR[id]) {
unite(edges[k].first, edges[k].second, true);
}
res[id] += cc - P[id] - 1;
rollback();
}
for (int id : cands) {
cant[id] = false;
}
}
return res;
}
#ifdef ngu
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef ngu
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n, C, Q;
cin >> n >> C >> Q;
vector<int> T(C), X(C), Y(C);
for (int i = 0; i < C; ++i) {
cin >> T[i] >> X[i] >> Y[i];
}
vector<int> W(Q), P(Q);
for (int i = 0; i < Q; ++i) {
cin >> W[i] >> P[i];
}
auto res = simulateCollapse(n, T, X, Y, W, P);
for (int i = 0; i < Q; ++i) {
cout << res[i] << " ";
}
}
#endif ngu
