#include <bits/stdc++.h> #define time() cerr << " \n " << "Time : " << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." #define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i) #define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i) #define all(x) x.begin(), x.end() #define uni(x) x.erase(unique(all(x)), x.end()) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define dbg(...) cerr << "[ " << #__VA_ARGS__ << " ] = ", debug(__VA_ARGS__) template<typename T> void debug(T x) { cerr << x << "\n\n"; } template<typename T, typename... Args> void debug(T x, Args... args) { cerr << x << " , ", debug(args...); } // -------------------------------------------------------------------------------------------------------------------- const int maxn = 1e5 + 3; const int B = 317; int n, m, q, ans[maxn], timer[maxn]; struct Ed { int u, v, w, id; }; struct Qr { int op, x, y, id; }; Ed Feds[maxn]; int InEds[405][maxn]; Qr qrs[maxn]; bool markEd[maxn]; // -------------------------------------------------------------------------------------------------------------------- struct DSU { vector<int> e; vector<pair<int &, int>> history; void init() {e.clear(); e.assign(n + 3, -1);} int get(int u) {return e[u] < 0 ? u : get(e[u]);} bool unite(int u, int v) { u = get(u); v = get(v); if (u == v) return false; if (e[u] > e[v]) swap(u, v); history.push_back({e[u], e[u]}); history.push_back({e[v], e[v]}); e[u] += e[v]; e[v] = u; return true; } int versions() {return (int)history.size();} void rollback(int until) { while (history.size() > until) { history.back().first = history.back().second; history.pop_back(); } } } dsu; bool cmpE(const int &x, const int &y) { return Feds[x].w > Feds[y].w; } bool cmpQ(const Qr &A, const Qr &B) { return A.y < B.y; } void solve() { cin >> n >> m; FOR(i, 1, m) { int u, v, w; cin >> u >> v >> w; if (u > v) swap(u, v); Feds[i].u = u; Feds[i].v = v; Feds[i].w = w; Feds[i].id = i; } cin >> q; FOR(iq, 1, q) { cin >> qrs[iq].op >> qrs[iq].x >> qrs[iq].y; qrs[iq].id = iq; } FOR(bl, 0, q / B) { int sta = max(1, bl * B), ed = min(q, (bl + 1) * B - 1); if (sta > ed) break; dsu.init(); FOR(i, 1, m) { markEd[i] = true; } FOR(iq, sta, ed) { if (qrs[iq].op != 1) continue; markEd[qrs[iq].x] = false; } vector<int> unchange, change; FOR(i, 1, m) { if (!markEd[i]) { change.push_back(i); continue; } unchange.push_back(i); } sort(all(unchange), cmpE); sort(all(change)); FOR(i, 0, (int)change.size() - 1) InEds[0][i] = Feds[change[i]].w; FOR(iq, sta, ed) { int riq = iq - sta + 1; FOR(i, 0, (int)change.size() - 1) InEds[riq][i] = InEds[riq - 1][i]; if (qrs[iq].op != 1) continue; int cur_id = lower_bound(all(change), qrs[iq].x) - change.begin(); InEds[riq][cur_id] = qrs[iq].y; } for (const int &id : unchange) { timer[id] = dsu.versions(); dsu.unite(Feds[id].u, Feds[id].v); } sort(qrs + sta, qrs + ed + 1, cmpQ); FOR(iq, sta, ed) { if (qrs[iq].op != 2) continue; while (unchange.size() && Feds[unchange.back()].w < qrs[iq].y) { dsu.rollback(timer[unchange.back()]); unchange.pop_back(); } int time = dsu.versions(); int riq = qrs[iq].id - sta + 1; FOR(i, 0, (int)change.size() - 1) { if (InEds[riq][i] >= qrs[iq].y) { dsu.unite(Feds[change[i]].u, Feds[change[i]].v); } } ans[qrs[iq].id] = -dsu.e[dsu.get(qrs[iq].x)]; dsu.rollback(time); } FOR(i, 0, (int)change.size() - 1) { Feds[change[i]].w = InEds[ed - sta + 1][i]; } } FOR(i, 1, q) if (ans[i] != 0) cout << ans[i] << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define TASK "test" if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); freopen(TASK".OUT", "w", stdout); } solve(); time(); return 0; }

bridges.cpp: In function 'int main()':
bridges.cpp:196:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:197:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~