#include<bits/stdc++.h> using namespace std; const int N=2e3+5; const int M=4e6+5; int n,m; int rx[N],ry[N]; int dis[M]; int tai; bool inq[M]; int dx[]={0,0,0,1,-1}; int dy[]={0,1,-1,0,0}; struct node{ int x,y; }q[M]; int id(int x,int y){ return (x-1)*n+y; } void update(int x,int kx,int ky){ rx[x]=kx; ry[x]=ky; } int query(int xa,int ya,int xb,int yb){ for(int i=1;i<=n*n;i++){ dis[i]=(int)1e9; q[i].x=q[i].y=0; inq[i]=false; } tai=0; dis[id(xa,ya)]=0; node sta={xa,ya}; q[++tai]=sta; // cout<<dis[id(q[tai].x,q[tai].y)]<<" "; while(tai!=0){ int x=q[tai].x,y=q[tai--].y; inq[id(x,y)]=false; // cout<<x<<" "<<y<<": \n"; for(int i=1;i<=4;i++){ int nx=x+dx[i],ny=y+dy[i]; // if(x==4&&y==2) cout<<"RUn here\n"; if(nx<1||ny<1||nx>n||ny>n) continue; if(max(x,y)!=max(nx,ny)&&((x==nx&&ry[min(y,ny)]!=x)||(y==ny&&(rx[min(x,nx)]!=y)))) continue; // cout<<dis[id(nx,ny)]<<" "<<dis[id(x,y)]<<"\n"; if(dis[id(nx,ny)]>dis[id(x,y)]+1){ dis[id(nx,ny)]=dis[id(x,y)]+1; // cout<<"("<<x<<","<<y<<")--->("<<nx<<","<<ny<<"): "<<a[id(x,y)][id(nx,ny)]<<"\n"; if(inq[id(nx,ny)]==false){ inq[id(nx,ny)]=true; node nxt={nx,ny}; q[++tai]=nxt; } } } } // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++){ // cout<<dis[id(i,j)]<<" "; // } // cout<<"\n"; // } return dis[id(xb,yb)]; } int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<n;i++) cin>>rx[i]>>ry[i]; // cout<<a[id(4,2)][id(3,2)]<<" "; // for(int i=1;i<=n*n;i++){ // for(int j=1;j<=n*n;j++){ // cout<<a[i][j]<<" "; // } // cout<<"\n"; // } while(m--){ int opt,x,y,z,c; cin>>opt>>x>>y>>z; if(opt==1) update(x,y,z); else{ cin>>c; cout<<query(x,y,z,c)<<"\n"; } } return 0; }