#include <bits/stdc++.h>
using namespace std;
/*
DSU rollback + block decomposition
Cải tiến so với code gốc:
- dùng mảng tĩnh cho record stack (không dùng vector)
- tag/version để mark changed edges trong block (reset O(1))
- một vài micro-optimizations
*/
#define SIZE __size__
#define UNION __union__
#define DATA __data__
const int MAXM = 100009;
const int MAXQ = 100009;
const int MAXN = 100009;
const int CAN = 350; // kích thước block, có thể tune
int n, m, q;
struct Edge {
int u, v, w, index;
} edge[MAXM];
bool dummy_changed[MAXM]; // không dùng trực tiếp, dùng tag below
// tag/version để biết edge bị thay trong block
int tag_changed[MAXM];
int cur_tag = 1;
// để lưu lần đầu xử lý trong block (firsttime logic)
int firsttime[MAXM];
int uniq = 1;
int root_arr[MAXN], sz_arr[MAXN];
int getroot_simple(int x) {
return (root_arr[x] == x ? x : root_arr[x] = getroot_simple(root_arr[x]));
}
void union_simple(int a, int b) {
a = getroot_simple(a);
b = getroot_simple(b);
if (a == b) return;
root_arr[a] = b;
sz_arr[b] += sz_arr[a];
}
// DSU rollback record entry (mảng tĩnh)
struct REC {
int node; // node index whose parent/size changed
int root_before; // previous parent
int size_before; // previous size[node]
};
const int MAX_RECORDS = 2000000; // tune nếu cần
REC record_stack[MAX_RECORDS];
int rec_top = 0;
// rollback-aware getroot (path comp without destroying info)
int getroot_record(int x) {
while (root_arr[x] != x) x = root_arr[x];
return x;
}
// version of getroot that records changes for rollback
int getroot_and_record(int x) {
if (root_arr[x] == x) return x;
int p = getroot_and_record(root_arr[x]);
// record current node's parent and size before changing
record_stack[rec_top++] = { x, root_arr[x], sz_arr[x] };
root_arr[x] = p;
return p;
}
void union_record(int a, int b) {
a = getroot_and_record(a);
b = getroot_and_record(b);
if (a == b) return;
// record a before linking
record_stack[rec_top++] = { a, root_arr[a], sz_arr[a] };
root_arr[a] = b;
// record b before size update
record_stack[rec_top++] = { b, root_arr[b], sz_arr[b] };
sz_arr[b] += sz_arr[a];
}
void rollback_to(int old_top) {
while (rec_top > old_top) {
--rec_top;
REC r = record_stack[rec_top];
root_arr[r.node] = r.root_before;
sz_arr[r.node] = r.size_before;
}
}
struct Query {
int op, x, y, index;
} ask[MAXQ];
Edge bridges[MAXQ]; // store edges for updates inside block
int answer[MAXQ];
// helper array for sorting edges by weight (indices)
int order_idx[MAXM];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> m)) return 0;
for (int i = 1; i <= m; ++i) {
cin >> edge[i].u >> edge[i].v >> edge[i].w;
edge[i].index = i;
}
cin >> q;
// init tags/firsttime
for (int i = 1; i <= m; ++i) {
tag_changed[i] = 0;
firsttime[i] = 0;
}
// process queries block by block
int block_id = 0;
for (int start = 1; start <= q; start += CAN) {
++block_id;
int l = start;
int r = min(q, start + CAN - 1);
// read block queries
for (int i = l; i <= r; ++i) {
cin >> ask[i].op >> ask[i].x >> ask[i].y;
ask[i].index = i;
if (ask[i].op == 1) {
// mark changed using tag
tag_changed[ask[i].x] = block_id;
bridges[i] = edge[ask[i].x]; // store prior edge state
}
}
// Build an index array of edges sorted by current weight
// (We will skip edges that are changed in this block via tag_changed)
for (int i = 1; i <= m; ++i) order_idx[i-1] = i;
sort(order_idx, order_idx + m, [&](int a, int b){
if (edge[a].w != edge[b].w) return edge[a].w < edge[b].w;
return a < b;
});
// init DSU
for (int i = 1; i <= n; ++i) {
root_arr[i] = i; sz_arr[i] = 1;
}
// collect queries of type 2 (contain) with their index and sort descending by y
static Query contain[CAN + 5];
int contain_cnt = 0;
for (int i = l; i <= r; ++i) {
if (ask[i].op == 2) contain[contain_cnt++] = ask[i];
}
sort(contain, contain + contain_cnt, [](const Query &a, const Query &b){
return a.y > b.y; // descending by y
});
// process contain queries using pointer on sorted edges (descending)
int ptr = m - 1; // order_idx[ptr] is current largest weight candidate
for (int ci = 0; ci < contain_cnt; ++ci) {
Query d = contain[ci];
int minimum = d.y;
int island = d.x;
// add all global edges (not changed in this block) with w >= minimum
while (ptr >= 0 && edge[order_idx[ptr]].w >= minimum) {
int ei = order_idx[ptr];
if (tag_changed[ei] != block_id) {
union_simple(edge[ei].u, edge[ei].v);
}
--ptr;
}
// now we need to incorporate changed edges from this block
int old_top = rec_top;
++uniq;
// scan left of query in block
for (int i = d.index - 1; i >= l; --i) {
if (ask[i].op != 1) continue;
Edge br = bridges[i];
int w_for_this = ask[i].y;
int idx = br.index;
if (firsttime[idx] == uniq) continue;
firsttime[idx] = uniq;
if (w_for_this >= minimum) union_record(br.u, br.v);
}
// scan right of query in block
for (int i = d.index + 1; i <= r; ++i) {
if (ask[i].op != 1) continue;
Edge br = bridges[i];
int w_for_this = ask[i].y;
int idx = br.index;
if (firsttime[idx] == uniq) continue;
firsttime[idx] = uniq;
if (br.w >= minimum) union_record(br.u, br.v);
}
// but note: for updates that appear in block, there are two relevant weights:
// - for updates before d.index, the effective weight is ask[i].y (the new weight)
// - for updates after d.index, the effective weight is br.w (previous weight)
// The code above handles that: left uses ask[i].y, right uses br.w.
// answer: size of component containing island
int comp_root = getroot_simple(island);
// However, some nodes may have been path-compressed in union_record; to get correct size,
// we should get root via getroot_and_record or getroot_simple (we maintained sz only for roots)
answer[d.index] = sz_arr[getroot_simple(island)];
// rollback to old_top
rollback_to(old_top);
}
// after processing block, apply updates (op==1) permanently to edges
for (int i = l; i <= r; ++i) {
if (ask[i].op == 1) {
int ei = ask[i].x;
edge[ei].w = ask[i].y;
// clear tag by just leaving it; next block uses different block_id
}
}
}
// print answers for op==2
for (int i = 1; i <= q; ++i) {
if (ask[i].op == 2) {
cout << answer[i] << '\n';
}
}
return 0;
}
