#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops,Ofast") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,tune=native") #define all(x) x.begin(), x.end() const int mxN = 50055; int par[mxN], sz[mxN]; vector<pair<int,int>> his; void reset(int n){ for(int i = 1; i <= n; ++i) par[i] = i, sz[i] = 1; } int find(int u){ while(par[u] != u) u = par[u]; return u; } bool unite(int u, int v){ u = find(u); v = find(v); if(u == v) return false; if(sz[u] < sz[v]) swap(u, v); his.push_back({v, u}); par[v] = u; sz[u] += sz[v]; return true; } void rollback(int cnt){ assert(cnt <= (int)his.size()); while(cnt--){ auto [v, u] = his.back(); his.pop_back(); par[v] = v; sz[u] -= sz[v]; } } signed main(){ ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); int n, m, q; cin >> n >> m; vector<tuple<int, int, int>> edge, query; for(int i = 1, u, v, d; i <= m; ++i){ cin >> u >> v >> d; edge.push_back({u, v, d}); } cin >> q; for(int i = 1, t, u, v; i <= q; ++i){ cin >> t >> u >> v; if(t == 1) --u; query.push_back({t, u, v}); } int nsqrt = 1001; vector<int> ans(q + 5, -1); for(int i = 0; i < (int) query.size(); i += nsqrt){ int j = min((int) query.size() - 1, i + nsqrt - 1); vector<pair<int, int>> upd, ask; vector<tuple<int, int, int>> use; bool changed[m + 1] = {0}; reset(n); for(int k = i; k <= j; ++k){ auto [t, u, v] = query[k]; if(t == 1){ changed[u] = 1; upd.push_back({u, v}); }else{ ask.push_back({v, k}); } } vector<int> fk; for(int j = 0; j < m; ++j){ auto [u, v, d] = edge[j]; if(!changed[j]) { use.push_back({u, v, d}); }else{ fk.push_back(j); } } sort(all(use), [&](tuple<int, int, int> d1, tuple<int, int, int> d2){ return get<2>(d1) > get<2>(d2); }); sort(all(ask), [&](pair<int, int> p1, pair<int, int> p2){ return p1.first > p2.first; }); int ptr = 0; for(auto [w, idx] : ask){ while(ptr < (int) use.size() && get<2>(use[ptr]) >= w){ unite(get<0>(use[ptr]), get<1>(use[ptr])); ptr += 1; } vector<bool> seen(m + 1, 0); int cnt = 0; for(int k = idx - 1; k >= i; --k){ auto [t, u, v] = query[k];; if(t == 1 && !seen[u] && v >= w){ auto [u1, v1, d] = edge[u]; if(unite(u1, v1)) cnt += 1; } if(t == 1) seen[u] = 1; } for(auto it : fk){ auto [u, v, d] = edge[it]; if(!seen[it] && d >= w){ if(unite(u, v)) { cnt += 1; } } } auto [t, u, v] = query[idx]; assert(v == w); ans[idx] = sz[find(u)]; rollback(cnt); } for(auto [eid, val] : upd){ get<2>(edge[eid]) = val; } } for(int i = 0; i <= q; ++i){ if(ans[i] != -1) cout << ans[i] << "\n"; } return 0; }