#include #include #include #include #include #include #include #include #include #include #include #include #define vll vector #define vvvl vector #define vvl vector> #define VV(a, b, c, d) vector >(a, vector(b, c)) #define VVV(a, b, c, d) vector(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c> G; vector> rG; vector used; vector cmp; vector vs; Graph(ll V){ MAX_V = V; G = vector>(MAX_V+1); rG = vector>(MAX_V+1); used.resize(MAX_V+1, false); cmp.resize(MAX_V+1, 0); } void add_edge(int from, int to){ G[from].insert(to); G[to].insert(from); rG[from].insert(to); rG[to].insert(from); } void dfs(int v){ used[v] = true; for(auto to:G[v]) { ll a = v, b = to; G[b].erase(a); rG[a].erase(b); if(!used[to]) dfs(to); } vs.push_back(v); } void rdfs(int v, int k){ used[v] = true; cmp[v] = k; for(auto to:rG[v]) { if(!used[to]) rdfs(to, k); } } int scc(int V){ for(int i=0;i=0;i--) if(!used[vs[i]]) rdfs(vs[i], k++); return k; } //変換後の頂点->辺群 vvl build(ll n){ vvl ret = VV(MAX_V+1, 0, 0, ll); vector> T(MAX_V+1); scc(n); for(int i=0;i<=n;i++){ for(auto to:G[i]){ T[cmp[i]].insert(cmp[to]); T[cmp[to]].insert(cmp[i]); } } for(int i=0;i<=n;i++){ for(auto to:T[i]){ ret[i].push_back(to); } } return ret; } }; template< typename G > struct HeavyLightDecomposition { G &g; vector< int > sz, in, out, head, rev, par; HeavyLightDecomposition(G &g) : g(g), sz(100001), in(100001), out(100001), head(100001), rev(100001), par(100001) {} void dfs_sz(int idx, int p) { par[idx] = p; sz[idx] = 1; if(g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back()); for(auto &to : g[idx]) { if(to == p) continue; dfs_sz(to, idx); sz[idx] += sz[to]; if(sz[g[idx][0]] < sz[to]) swap(g[idx][0], to); } } void dfs_hld(int idx, int par, int ×) { in[idx] = times++; rev[in[idx]] = idx; for(auto &to : g[idx]) { if(to == par) continue; head[to] = (g[idx][0] == to ? head[idx] : to); dfs_hld(to, idx, times); } out[idx] = times; } void build() { dfs_sz(0, -1); int t = 0; dfs_hld(0, -1, t); } int la(int v, int k) { while(1) { int u = head[v]; if(in[v] - k >= in[u]) return rev[in[v] - k]; k -= in[v] - in[u] + 1; v = par[u]; } } int lca(int u, int v) { for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) return u; } } template< typename T, typename Q, typename F > T query(int u, int v, const T &ti, const Q &q, const F &f, bool edge = false) { T l = ti, r = ti; for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v), swap(l, r); if(head[u] == head[v]) break; l = f(q(in[head[v]], in[v] + 1), l); } return f(f(q(in[u] + edge, in[v] + 1), l), r); // return {f(q(in[u] + edge, in[v] + 1), l), r}; } template< typename Q > void add(int u, int v, const Q &q, bool edge = false) { for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) break; q(in[head[v]], in[v] + 1); } q(in[u] + edge, in[v] + 1); } }; //------------------------------------------------------------------- //------------------------------------------------------------------- struct segtree{ ll M=1, INF = 1000000000000000000, INIT; vector dat; segtree(ll N, ll num){ INIT = num; while(M0) { k = (k-1)/2; dat[k] = max(dat[k*2+1], dat[k*2+2]); } } vll query(ll a, ll b=-1, ll k=0, ll l=0, ll r=-1){ if(r==-1) r = M; if(b==-1) b = M; if(r<=a || b<=l) return vll{INIT, -INIT}; if(a<=l && r<=b) return dat[k]; vll A = query(a, b, k*2+1, l, (l+r)/2); vll B = query(a, b, k*2+2, (l+r)/2, r); return max(A, B); } }; //------------------------------------------------------------------- #include int main(int argc, char const *argv[]) { ll a, b, c, n, m, q;std::cin >> n >> m >> q; Graph scc(n+1); re(i, m){ scanf("%lld %lld", &a, &b); scc.add_edge(a, b); } vvl G = scc.build(n); HeavyLightDecomposition hld(G); hld.build(); segtree seg(100001, -1); vector> max_cost(100001); re(i, q){ scanf("%lld %lld %lld", &a, &b, &c); if(a==1){ b = scc.cmp[b]; max_cost[b].push(c); ll MAX = max_cost[b].top(); hld.add(b, b, [&](ll x, ll y){seg.update(vll{MAX, b}, x);}); }else{ b = scc.cmp[b]; c = scc.cmp[c]; vll q = hld.query(b, c, vll{-1, -1}, [&](ll x, ll y){return seg.query(x, y);}, [&](vll x, vll y){return max(x, y);} ); printf("%lld\n", q[0]); if(q[0]!=-1) { max_cost[q[1]].pop(); ll MAX = (!max_cost[q[1]].empty()?max_cost[q[1]].top():-1); hld.add(q[1], q[1], [&](ll x, ll y){seg.update(vll{MAX, q[1]}, x);}); } } } return 0; }