#include using namespace std; #define rep(i, n) for(long long i=0;i<(long long)(n);i++) #define REP(i,k,n) for(long long i=k;i<(long long)(n);i++) #define all(a) a.begin(),a.end() #define rsort(a) {sort(all(a));reverse(all(a));} #define pb emplace_back #define eb emplace_back #define lb(v,k) (lower_bound(all(v),(k))-v.begin()) #define ub(v,k) (upper_bound(all(v),(k))-v.begin()) #define fi first #define se second #define pi M_PI #define PQ(T) priority_queue #define SPQ(T) priority_queue,greater> #define dame(a) {out(a);return 0;} #define decimal cout< P; typedef tuple PP; typedef tuple PPP; typedef multiset S; using vi=vector; using vvi=vector; using vvvi=vector; using vvvvi=vector; using vp=vector

; using vvp=vector; using vpp=vector; using vb=vector; using vvb=vector; using vvvb=vector; const ll inf=1001001001001001001; const ll INF=1001001001; const ll mod=1000000007; const double eps=1e-10; template bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;} template bool chmax(T&a,T b){if(a void out(T a){cout< void outp(T a){cout<<'('< void outvp(T v){rep(i,v.size())cout<<'('< void outvvp(T v){rep(i,v.size())outvp(v[i]);} template void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout< void outvv(T v){rep(i,v.size())outv(v[i]);} template bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);} template void yesno(T b){if(b)out("yes");else out("no");} template void YesNo(T b){if(b)out("Yes");else out("No");} template void YESNO(T b){if(b)out("YES");else out("NO");} template void noyes(T b){if(b)out("no");else out("yes");} template void NoYes(T b){if(b)out("No");else out("Yes");} template void NOYES(T b){if(b)out("NO");else out("YES");} void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);} ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);} ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} P ans; class segtree{ vp seg;ll N=1; vector> pq; public: segtree(ll n){ pq=vector>(n); while(N0){ i=(i-1)/2; seg[i]=max(seg[i*2+1],seg[i*2+2]); } } P ma(ll a,ll b,ll k,ll l,ll r){ if(a<=l&&r<=b)return seg[k]; if(r<=a||b<=l)return P(-1,-1); return max(ma(a,b,k*2+1,l,(l+r)/2),ma(a,b,k*2+2,(l+r)/2,r)); } void query(ll a,ll b){ chmax(ans,ma(a,b,0,0,N)); // outp(P(a,b)); } void erase(ll i){ pq[i].pop();if(pq[i].empty())pq[i].push(-1); update(i,pq[i].top()); } void add(ll i,ll x){ pq[i].push(x); update(i,pq[i].top()); } }; class UF{ vi data;stack

st; public: UF(ll n){ data=vi(n,1); } bool merge(ll x,ll y,bool undo=false){ x=root(x);y=root(y); if(data[x]>data[y])swap(x,y); if(undo){st.emplace(y,data[y]);st.emplace(x,data[x]);} if(x==y)return false; data[y]+=data[x];data[x]=-y; return true; } ll root(ll i){if(data[i]>0)return i;return root(-data[i]);} ll getsize(ll i){return data[root(i)];} bool same(ll a,ll b){return root(a)==root(b);} void undo(){rep(i,2){data[st.top().fi]=st.top().se;st.pop();}} }; int main(){ ll n,m,q;cin>>n>>m>>q; vvp g(n);vp edge(m);UF uf(n); rep(i,m){ ll a,b;cin>>a>>b;a--;b--; g[a].pb(b,i);g[b].pb(a,i); edge[i]=P(a,b); } vb bridge(m,false); vi dep(n,-1); function lk=[&](ll i,ll e,ll p,ll d){ dep[i]=d; ll res=n+100; for(auto x:g[i])if(x.se!=e){ if(dep[x.fi]!=-1)chmin(res,dep[x.fi]); else chmin(res,lk(x.fi,x.se,i,d+1)); } if(res>=dep[i]&&e!=-1)bridge[e]=true; else if(e!=-1)uf.merge(i,p); return res; }; vi root; rep(i,n)if(dep[i]==-1){ lk(i,-1,-1,0); root.pb(i); } vi num(n,-1);ll c=0; function makenum=[&](ll i){ if(uf.root(i)==i)num[i]=c++; for(auto x:g[i])if(dep[x.fi]==dep[i]+1)makenum(x.fi); }; for(ll r:root)makenum(r); vvi tree(c); rep(i,m)if(bridge[i]){ ll a=num[uf.root(edge[i].fi)],b=num[uf.root(edge[i].se)]; tree[a].pb(b);tree[b].pb(a); } vi par(c),head(c),id(c),sz(c,1); ll cnt=0; function init=[&](ll i,ll p){ par[i]=p; P ma=P(0,0); rep(j,tree[i].size())if(tree[i][j]!=p){ init(tree[i][j],i); sz[i]+=sz[tree[i][j]]; chmax(ma,P(sz[tree[i][j]],j)); } swap(tree[i][0],tree[i][ma.se]); }; init(0,-1); function HLD=[&](ll i,ll p){ id[i]=cnt++; rep(j,tree[i].size())if(tree[i][j]!=p){ if(j)head[tree[i][j]]=tree[i][j]; else head[tree[i][j]]=head[i]; HLD(tree[i][j],i); } }; HLD(0,-1); segtree seg(c); function query=[&](ll a,ll b){ ll A=head[a],B=head[b]; if(A==B)seg.query(min(id[a],id[b]),max(id[a],id[b])+1); else if(id[A]>md; if(md==2){ ans=P(-1,-1); ll x,y;cin>>x>>y;x--;y--;x=num[uf.root(x)];y=num[uf.root(y)]; query(x,y); out(ans.fi); if(ans.fi!=-1)seg.erase(ans.se); } else{ ll i,a;cin>>i>>a;i--;i=num[uf.root(i)]; seg.add(id[i],a); } } }