#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i ) #define rep(i,n) REP(i,0,n) typedef long long ll; typedef pair pint; typedef pair pli; const int inf=1e9+7; const ll longinf=1LL<<60 ; const ll mod=1e9+7 ; int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ; typedef vector> graph; struct LowLink{ graph v,nv; vector art,low,ord,idx; vector bridge; LowLink(int n):v(n),ord(n,-1),low(n),idx(n,-1){}; void addedge(int x,int y){ v[x].push_back(y); v[y].push_back(x); } bool isbridge(int x,int y){ if(ord[x]>ord[y])swap(x,y); return ord[x]1)isart=true; if(isart)art.push_back(x); } void dfs(){ int count=0; dfs(count,-1,0); } graph build(){ dfs(); int k=0; idx[0]=0; stack st; st.push(0); while(!st.empty()){ int x=st.top();st.pop(); for(auto to:v[x]){ if(idx[to]!=-1)continue; if(isbridge(x, to))idx[to]=++k; else idx[to]=idx[x]; st.push(to); } } nv.resize(k+1); for(pint e:bridge){ nv[idx[e.first]].push_back(idx[e.second]); nv[idx[e.second]].push_back(idx[e.first]); } return nv; } }; struct SegmentTree{ private: int n; vector node; public: SegmentTree(int sz,ll init){ n=1; while(n0){ k=(k-1)/2; node[k]=max(node[2*k+1],node[2*k+2]); } } //[a,b)でのminを返す ll get(int a,int b,int k=0,int l=0,int r=-1){ if(r<0)r=n; if(r<=a||b<=l)return -1; if(a<=l&&r<=b)return node[k]; ll xl=get(a,b,2*k+1,l,(l+r)/2); ll xr=get(a,b,2*k+2,(l+r)/2,r); return max(xl,xr); } }; SegmentTree sg(101010,-1); struct HLDecomposition{ int n,pos; vector> v; vector idx,head,sz,hvy,par,depth,inv,type; HLDecomposition(){}; HLDecomposition(int s): n(s),pos(0),v(n),idx(n,-1),head(n),sz(n,1), hvy(n,-1),par(n),depth(n),inv(n),type(n){} HLDecomposition(vector> nv): n(nv.size()),pos(0),v(nv),idx(n,-1),head(n),sz(n,1), hvy(n,-1),par(n),depth(n),inv(n),type(n){} void addedge(int x,int y){ v[x].push_back(y); v[y].push_back(x); } void dfs(int rt){ par[rt]=-1; depth[rt]=0; stack st; st.push({rt,0}); while(!st.empty()){ int x=st.top().first; int& i=st.top().second; if(i<(int)v[x].size()){ int to=v[x][i++]; if(to==par[x])continue; par[to]=x; depth[to]=depth[x]+1; st.push({to,0}); } else { st.pop(); int res=0; for(int to:v[x]){ if(to==par[x])continue; sz[x]+=sz[to]; if(sz[to]>res)res=sz[to],hvy[x]=to; } } } } void bfs(int r,int c){ int &k=pos; queue q; q.push(r); while(!q.empty()){ int h=q.front();q.pop(); for(int x=h;x!=-1;x=hvy[x]){ type[x]=c; head[x]=h; idx[x]=k++; inv[idx[x]]=x; for(int to:v[x]) if(to!=par[x]&&to!=hvy[x])q.push(to); } } } void build(vector rs=vector(1,0)){ int c=0; for(int r:rs){ dfs(r); bfs(r,c++); } } int f(int x,int y){ //ここに何か書く!!! return sg.get(x,y+1); } int for_v(int x,int y){ int res=-1; while(1){ if(idx[x]>idx[y])swap(x,y); res=max(res,f(max(idx[head[y]],idx[x]),idx[y])); if(head[x]!=head[y])y=par[head[y]]; else break; } return res; } void for_edge(int x,int y){ while(1){ if(idx[x]>idx[y])swap(x,y); if(head[x]!=head[y]){ f(idx[head[y]],idx[y]); y=par[head[y]]; } else{ if(x!=y)f(idx[x]+1,idx[y]); break; } } } int lca(int x,int y){ while(1){ if(idx[x]>idx[y])swap(x,y); if(head[x]==head[y])return x; y=par[head[y]]; } } int dist(int x,int y){ return depth[x]+depth[y]-2*depth[lca(x,y)]; } }; int main(){ int n,m,q; cin>>n>>m>>q; LowLink ll(n); rep(i,m){ int x,y; cin>>x>>y; x--;y--; ll.addedge(x, y); } vector> nv=ll.build(); HLDecomposition hl(nv); hl.build(); map mp; priority_queue pq[n]; while(q--){ int c,x,y; cin>>c>>x>>y; if(c==1){ x--; x=hl.idx[ll.idx[x]]; mp[y]=x; pq[x].push(y); if(pq[x].top()==y)sg.update(x, y); } else{ --x;--y; x=ll.idx[x]; y=ll.idx[y]; int ret=hl.for_v(x, y); cout<