#include #pragma GCC optimize("O3") #pragma GCC target("avx") #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)< P; typedef pair pll; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector vvl; typedef vector vd; typedef vector

vp; typedef vector vs; const int MAX_N = 100005; #define getchar getchar_unlocked #define putchar putchar_unlocked int in() { int n = 0; short c; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } void out(int n) { short res[10], i = 0; do { res[i++] = n % 10, n /= 10; } while (n); while (i) putchar(res[--i] + '0'); putchar('\n'); } struct HLdecomposition{ struct Centroid{ int parid, pardepth, depth, sz; Centroid(int idx, int dep, int deep, int size) : parid(idx), pardepth(dep), depth(deep), sz(size){} P Up(){ return P(parid, pardepth); } }; vector > G; vector stsize, nxpath; vector pathorder, pathid; vector centroids; vector index; void Buildstsize(){ stack

s; s.push(P(0, -1)); while(!s.empty()) { P p = s.top(); s.pop(); if(stsize[p.first] != -1){ nxpath[p.first] = -1; for(int to : G[p.first]){ //親に向かう場合 if(p.second == to){ continue; } stsize[p.first] += stsize[to]; if(nxpath[p.first] == -1 || stsize[nxpath[p.first]] < stsize[to]) { nxpath[p.first] = to; } } }else{ s.push(p); stsize[p.first] = 1; for(int to : G[p.first]){ if(p.second != to){ s.push(P(to, p.first)); } } } } } void BuildPath() { stack

s; centroids.emplace_back(-1, -1, 0, 0); s.push(P(0, -1)); pathorder[0] = 0; while(!s.empty()) { P p = s.top(); s.pop(); pathid[p.first] = centroids[pathorder[p.first]].sz; for(int to : G[p.first]){ if(p.second == to) continue; if(to == nxpath[p.first]){ // Centroid-Pathについて pathorder[to] = pathorder[p.first]; }else{ // Centroid-Pathでないものについて pathorder[to] = (int)centroids.size(); centroids.emplace_back(pathorder[p.first], pathid[p.first], centroids[pathorder[p.first]].depth + 1,0); } s.emplace(to, p.first); } centroids[pathorder[p.first]].sz++; } } void Build_index(){ int ptr = 0; for(auto& centroid : centroids){ index.push_back(ptr); ptr += centroid.sz; } } void add_edge(int x, int y) { G[x].push_back(y), G[y].push_back(x); } void build() { Buildstsize(); BuildPath(), Build_index(); } P info(int idx) { return P(pathorder[idx], pathid[idx]); } int get(int a) { P p = info(a); return (index[p.first] + p.second); } void query(int a, int b, const function< void(int, int) > &func) { int pathidA, pathdepthA, pathidB, pathdepthB; tie(pathidA, pathdepthA) = info(a); tie(pathidB, pathdepthB) = info(b); while(pathidA != pathidB) { if(centroids[pathidA].depth > centroids[pathidB].depth) { func(index[pathidA], index[pathidA] + pathdepthA + 1); tie(pathidA, pathdepthA) = centroids[pathidA].Up(); }else{ func(index[pathidB], index[pathidB] + pathdepthB + 1); tie(pathidB, pathdepthB) = centroids[pathidB].Up(); } } if(pathdepthA > pathdepthB) swap(pathdepthA, pathdepthB); func(index[pathidA] + pathdepthA, index[pathidA] + pathdepthB + 1); } HLdecomposition(){}; void construct(int node_size) { G.resize(node_size); stsize.assign(node_size, -1); nxpath.resize(node_size); pathorder.resize(node_size); pathid.resize(node_size); } }; class biconnected{ public: vector > G,tree; vector ord,low,cmp; vector > check; vector

bridge; vector visit; int V,kind; biconnected(int node_size){ V = node_size; kind = 0; G.resize(V); check.resize(V),ord.resize(V),low.resize(V); cmp.resize(V),visit.resize(V,false); } void build(){ int id = 0; rep(i,V){ if(!visit[i]){ dfs(i,-1,id); } } } void dfs(int v,int p,int &k) { visit[v] = true; ord[v] = k++; low[v] = ord[v]; rep(i,(int)G[v].size()){ int w = G[v][i]; if(!visit[w]){ dfs(w,v,k); low[v] = min(low[v],low[w]); if(ord[v] < low[w]){ bridge.pb(P(v,w)); check[v][i].second = 1; check[w][check[v][i].first].second = 1; } //(v,w)は後退辺 }else if(w != p){ low[v] = min(low[v],ord[w]); } } } void add_edge(int u,int v) { G[u].push_back(v),G[v].push_back(u); check[u].push_back(P((int)check[v].size(),0)); check[v].push_back(P((int)check[u].size()-1,0)); } void restrict_dfs(int u,int p,int kind,queue& que) { visit[u] = true; cmp[u] = kind; rep(i,(int)G[u].size()){ int w = G[u][i]; if(check[u][i].second){ if(!visit[w]){ que.push(w); } }else if(!visit[w]){ restrict_dfs(w,u,kind,que); } } } void rebuild() { fill(visit.begin(),visit.end(),false); rep(i,V){ if(!visit[i]){ queue que; que.push(i); while(!que.empty()){ int p = que.front(); que.pop(); restrict_dfs(p,-1,kind,que); kind++; } } } } // auxiliary graph を作る void make_bctree(HLdecomposition& hl) { rebuild(); hl.construct(kind); rep(i,(int)bridge.size()){ hl.add_edge(cmp[bridge[i].first],cmp[bridge[i].second]); } } }; #define T int class segtree { private: int n,sz; vector > node; public: segtree(vector& v){ sz = (int)v.size(); n = 1; while(n < sz){ n *= 2; } node.resize(2*n); rep(i,sz){ node[i+n] = make_pair(v[i], i); } for(int i=n-1; i>=1; i--){ node[i] = min(node[2*i], node[2*i+1]); } } void update(int k, T a) { node[k+=n] = make_pair(a, k); while(k>>=1){ node[k] = min(node[2*k], node[2*k+1]); } } pair query(int a,int b,int k=0,int l=0,int r=-1) { pair res1 = make_pair(numeric_limits::max(), -1); pair res2 = make_pair(numeric_limits::max(), -1); a += n, b += n; while(a != b){ if(a % 2) cmn(res1, node[a++]); if(b % 2) cmn(res2, node[--b]); a >>= 1, b>>= 1; } return min(res1, res2); } void print() { rep(i,sz){ pair p; p = query(i,i+1); cout << "st[" << i << "]: " << p.fi << " " << p.se << endl; } } }; int main() { int n,m,q; n = in(), m = in(), q = in(); biconnected bc(n); rep(i,m){ int u = in(), v = in(); bc.add_edge(u-1,v-1); } bc.build(); HLdecomposition hl; bc.make_bctree(hl); hl.build(); int& kind = bc.kind; vi& cmp = bc.cmp; vi u(kind,0); vector > que(kind); vector mx(kind,0); vector trans(kind); vector unzip(kind); rep(i,kind){ int res = hl.get(i); trans[i] = res; unzip[res] = i; } segtree seg(u); rep(i,q){ int p,q,r; p = in(), q = in(), r = in(); if(p == 1){ int id = cmp[q-1]; que[id].push(r); if(mx[id] < r){ mx[id] = r; seg.update(trans[id],-r); } }else{ int id1 = cmp[q-1],id2 = cmp[r-1]; P ans = P(0,-1); hl.query(id1,id2,[&](int l, int r){ ans = min(ans,seg.query(l, r)); }); if(ans.fi == 0){ putchar('-'), putchar('1'), putchar('\n'); }else{ int real_id = unzip[ans.se]; que[real_id].pop(); if(que[real_id].empty()){ seg.update(ans.se,0); mx[real_id] = 0; }else{ int res = que[real_id].top(); seg.update(ans.se,-res); mx[real_id] = res; } out(-ans.fi); } } } }