#include <bits/stdc++.h>
using namespace std;
const int B = 1000; // K�ch th??c Block chia c?n t?i ?u
// C?u tr�c c?nh
struct Edge {
int u, v, w, id;
};
// C?u tr�c truy v?n
struct Query {
int type, b, r, s, w, id;
};
// C?u tr�c Rollback DSU
struct DSU {
vector<int> parent, sz;
vector<pair<int, int>> history; // L?u l?ch s? g?p ?? Rollback
DSU(int n) {
parent.resize(n + 1);
sz.resize(n + 1, 1);
for(int i = 1; i <= n; i++) parent[i] = i;
}
// T�m g?c (L?u �: KH�NG d�ng n�n ???ng ?? c� th? rollback)
int find(int i) {
if (i == parent[i]) return i;
return find(parent[i]);
}
// G?p 2 t?p h?p (Union by Size)
bool unite(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i == root_j) return false;
// Lu�n g?p c�y nh? v�o c�y l?n
if (sz[root_i] < sz[root_j]) swap(root_i, root_j);
history.push_back({root_j, root_i}); // root_j tr? th�nh con c?a root_i
parent[root_j] = root_i;
sz[root_i] += sz[root_j];
return true;
}
// L?y k�ch th??c th�nh ph?n li�n th�ng ch?a i
int get_size(int i) {
return sz[find(i)];
}
// Ho�n t�c l?i (Undo) 'steps' thao t�c g?p cu?i c�ng
void rollback(int steps) {
while (steps--) {
int child = history.back().first;
int root = history.back().second;
history.pop_back();
sz[root] -= sz[child]; // Tr? ?i k�ch th??c
parent[child] = child; // C?t ??t li�n k?t
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<Edge> edges(m + 1);
vector<int> edge_weight(m + 1); // L?u tr?ng t?i g?c c?a c�c c?nh
for (int i = 1; i <= m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
edges[i].id = i;
edge_weight[i] = edges[i].w;
}
int q;
cin >> q;
vector<Query> queries(q);
for (int i = 0; i < q; i++) {
cin >> queries[i].type;
if (queries[i].type == 1) {
cin >> queries[i].b >> queries[i].r; // Update: c?u b th�nh r
} else {
cin >> queries[i].s >> queries[i].w; // Query: t? s ?i xe tr?ng l??ng w
}
queries[i].id = i;
}
vector<int> ans(q, -1);
vector<bool> changed(m + 1, false);
// X? l� t?ng kh?i (Block) truy v?n
for (int l = 0; l < q; l += B) {
int r = min(q - 1, l + B - 1);
vector<Query> ask_queries;
vector<Query> update_queries;
vector<int> changed_edges_id;
// T�ch c�c truy v?n trong Block ra l�m 2 lo?i
for (int i = l; i <= r; i++) {
if (queries[i].type == 1) {
update_queries.push_back(queries[i]);
changed[queries[i].b] = true;
changed_edges_id.push_back(queries[i].b);
} else {
ask_queries.push_back(queries[i]);
}
}
// L?c c�c id c?nh b? thay ??i (x�a tr�ng l?p)
sort(changed_edges_id.begin(), changed_edges_id.end());
changed_edges_id.erase(unique(changed_edges_id.begin(), changed_edges_id.end()), changed_edges_id.end());
// T?p h?p c�c c?nh KH�NG b? ??i trong block n�y
vector<Edge> unchanged_edges;
for (int i = 1; i <= m; i++) {
if (!changed[i]) {
unchanged_edges.push_back(edges[i]);
}
}
// Sort truy v?n lo?i 2 gi?m d?n theo tr?ng l??ng xe
sort(ask_queries.begin(), ask_queries.end(),[](const Query& a, const Query& b) {
return a.w > b.w;
});
// Sort c?nh unchanged gi?m d?n theo tr?ng t?i
sort(unchanged_edges.begin(), unchanged_edges.end(),[](const Edge& a, const Edge& b) {
return a.w > b.w;
});
DSU dsu(n);
int ptr = 0;
// Duy?t t?ng truy v?n lo?i 2 ?� ???c sort
for (auto& query : ask_queries) {
// 1. ??a c�c c?nh UNCHANGED h?p l? v�o DSU (ch�ng s? n?m v?nh vi?n ? ?�y trong Block n�y)
while (ptr < unchanged_edges.size() && unchanged_edges[ptr].w >= query.w) {
dsu.unite(unchanged_edges[ptr].u, unchanged_edges[ptr].v);
ptr++;
}
int rollback_steps = 0;
// 2. X�t c�c c?nh CHANGED
// ??t l?i tr?ng t?i g?c c?a c�c c?nh changed tr??c block
for (int edge_id : changed_edges_id) {
edges[edge_id].w = edge_weight[edge_id];
}
// C?p nh?t ?� tr?ng t?i d?a v�o c�c truy v?n Update x?y ra TR??C truy v?n hi?n t?i
for (auto& upd : update_queries) {
if (upd.id < query.id) {
edges[upd.b].w = upd.r;
}
}
// Th�m c�c c?nh changed (n?u ?? ?i?u ki?n) v�o DSU
for (int edge_id : changed_edges_id) {
if (edges[edge_id].w >= query.w) {
if (dsu.unite(edges[edge_id].u, edges[edge_id].v)) {
rollback_steps++; // Ghi nh?n s? thao t�c union th�nh c�ng
}
}
}
// 3. L?y ?�p �n cho truy v?n hi?n t?i
ans[query.id] = dsu.get_size(query.s);
// 4. ROLLBACK: H?y c�c c?nh changed ra kh?i DSU
dsu.rollback(rollback_steps);
}
// K?t th�c block: C?p nh?t v?nh vi?n l?i m?ng g?c cho block sau
for (auto& upd : update_queries) {
edge_weight[upd.b] = upd.r;
edges[upd.b].w = upd.r;
}
for (int edge_id : changed_edges_id) {
changed[edge_id] = false; // Reset c?
}
}
// In k?t qu? cho c�c truy v?n lo?i 2
for (int i = 0; i < q; i++) {
if (ans[i] != -1) {
cout << ans[i] << "\n";
}
}
return 0;
}
