#include <bits/stdc++.h> using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1; for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch&15); return f*x; } int n,m,opt,a,b,c,d,x[200005],y[200005],col1,col2,col3,row1,row2,row3,lp[800005][2],rd[800005][2],vis[200005][2]; inline void pushup(int p,int lt,int rt,int kd){ if(~lp[p<<1][kd]) lp[p][kd]=lp[p<<1][kd]; else lp[p][kd]=lp[p<<1|1][kd]; if(~rd[p<<1|1][kd]) rd[p][kd]=rd[p<<1|1][kd]; else rd[p][kd]=rd[p<<1][kd]; } void build(int p,int lt,int rt,int kd){ if(lt==rt){ lp[p][kd]=rd[p][kd]=(vis[p][kd]?lt:-1); return ; } int mid=lt+rt>>1; build(p<<1,lt,mid,kd); build(p<<1|1,mid+1,rt,kd); pushup(p,lt,rt,kd); } void upd(int kd,int p,int lt,int rt,int pos,int val){ if(lt==rt){ vis[lt][kd]+=val; if(!vis[lt][kd]) lp[p][kd]=rd[p][kd]=-1; else lp[p][kd]=rd[p][kd]=lt; return ; } int mid=lt+rt>>1; if(mid>=pos) upd(kd,p<<1,lt,mid,pos,val); else upd(kd,p<<1|1,mid+1,rt,pos,val); pushup(p,lt,rt,kd); } inline int query1(int kd,int p,int lt,int rt,int l2,int r2){ if(l2<=lt&&rt<=r2) return rd[p][kd]; int mid=lt+rt>>1,res1=-1,res2=-1; if(mid>=l2) res1=query1(kd,p<<1,lt,mid,l2,r2); if(mid<r2) res2=query1(kd,p<<1|1,mid+1,rt,l2,r2); if(~res2) return res2; return res1; } inline int query2(int kd,int p,int lt,int rt,int l2,int r2){ if(l2<=lt&&rt<=r2) return lp[p][kd]; int mid=lt+rt>>1,res1=-1,res2=-1; if(mid>=l2) res1=query2(kd,p<<1,lt,mid,l2,r2); if(mid<r2) res2=query2(kd,p<<1|1,mid+1,rt,l2,r2); if(~res1) return res1; return res2; } inline int solve(int a,int b,int c,int d){ if(max(a,b)==max(c,d)) return abs(a-c)+abs(b-d); if(max(a,b)>max(c,d)) swap(a,c),swap(b,d); if(a>=b){ if(c>=d){ col1=query1(1,1,1,n,1,b),col2=query2(1,1,1,n,b,a),col3=query2(1,1,1,n,a,c),row1=query1(0,1,1,n,1,a); if(!(~col1)) col1=-1145141; if(!(~col2)) col2=1145141; if(!(~col3)) col3=c; if(!(~row1)) row1=-1145141; return min(min(abs(b-col1)+abs(d-col1),abs(b-col2)+abs(d-col2)),2*(a-row1)+abs(b-col3)+abs(d-col3)); } col1=query1(1,1,1,n,1,b),col2=query2(1,1,1,n,b,a),row1=query1(0,1,1,n,1,a),row2=query2(0,1,1,n,a,d); if(!(~col1)) col1=1145141; if(!(~col2)) col2=-1145141; if(!(~row2)) row2=d; if(!(~row1)) row1=-1145141; return min(min(abs(b-col1)+abs(a-row1)+abs(d-col1)+abs(c-row1),abs(b-col2)+ abs(a-row1)+abs(d-col2)+abs(c-row1)),min(abs(b-col1)+abs(a-row2)+abs(d-col1)+ abs(c-row2),min(abs(b-col2)+abs(a-row2)+abs(d-col2)+abs(c-row2),a-row1+d-b+abs(row1-c)))); } if(c>=d){ col1=query1(1,1,1,n,1,b),col2=query2(1,1,1,n,b,c),row1=query1(0,1,1,n,1,a),row2=query2(0,1,1,n,a,b); if(!(~col1)) col1=-1145141; if(!(~col2)) col2=c; if(!(~row2)) row2=1145141; if(!(~row1)) row1=-1145141; return min(min(abs(b-col1)+abs(a-row1)+abs(d-col1)+abs(c-row1),abs(b-col2)+ abs(a-row1)+abs(d-col2)+abs(c-row1)),min(abs(b-col1)+abs(a-row2)+abs(d-col1)+ abs(c-row2),min(abs(b-col2)+abs(a-row2)+abs(d-col2)+abs(c-row2),b-col1+c-a+abs(col1-d)))); } col1=query2(1,1,1,n,b,d),row1=query2(0,1,1,n,a,b),row2=query1(0,1,1,n,1,a),row3=query2(0,1,1,n,b,d); if(!(~col1)) col1=-1145141; if(!(~row2)) row2=1145141; if(!(~row3)) row3=d; if(!(~row1)) row1=-1145141; return min(min(abs(a-row1)+abs(c-row1),abs(a-row2)+abs(c-row2)),2*(col1-b)+abs(a-row3)+abs(c-row3)); } int main(){ n=read(),m=read(); for(int i=1;i<n;i++) x[i]=read(),y[i]=read(),vis[x[i]][1]++,vis[y[i]][0]++; build(1,1,n,0),build(1,1,n,1); while(m--){ opt=read(),a=read(),b=read(),c=read(); if(opt==1) upd(1,1,1,n,x[a],-1),upd(1,1,1,n,b,1),x[a]=b,upd(0,1,1,n,y[a],-1),upd(0,1,1,n,c,1),y[a]=c; else d=read(),printf("%d\n",solve(a,b,c,d)); } return 0; }