#include<bits/stdc++.h> #define id(i,j) ((((i)-1)*n)+(j)) #define add(u,v) t[++cnt].to=v,t[cnt].ne=h[u],h[u]=cnt using namespace std; struct node{ int to,ne; }t[5000005]; int h[10005],x[10005],y[10005],q[100005],dis[10005],n,cnt; bool inq[10005]; int spfa(int s,int e){ memset(dis,0x3f,sizeof(dis)); int he=1,ta=0; q[++ta]=s,dis[s]=0; while(he<=ta){ int now=q[he++]; inq[now]=0; for(int i=h[now];i;i=t[i].ne) if(dis[t[i].to]>dis[now]+1){ dis[t[i].to]=dis[now]+1; if(!inq[t[i].to]) q[++ta]=t[i].to,inq[t[i].to]=1; } } return dis[e]; } int main(){ int m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(i==j && i>1) add(id(i,j),id(i,j-1)),add(id(i,j-1),id(i,j)), add(id(i,j),id(i-1,j)),add(id(i-1,j),id(i,j)); else if(i<j && i>1) add(id(i,j),id(i-1,j)),add(id(i-1,j),id(i,j)); else if(j>i && j>1) add(id(i,j),id(i,j-1)),add(id(i,j-1),id(i,j)); } for(int j=1;j<n;j++){ scanf("%d%d",&x[j],&y[j]); for(int i=1;i<n;i++) add(id(i,x[j]),id(i+1,x[j])), add(id(i+1,x[j]),id(i,x[j])),add(id(y[j],i),id(y[j],i+1)), add(id(y[j],i+1),id(y[j],i)); } for(int i=1;i<=m;i++){ int opt,a,b,c,d; scanf("%d%d%d%d%d",&opt,&a,&b,&c,&d); printf("%lld\n",spfa(id(a,b),id(c,d))); } return 0; }/* Samples 1: Input: 4 5 1 1 1 2 2 1 2 2 4 4 3 2 4 4 3 3 2 1 2 3 3 2 2 2 4 4 2 1 4 2 3 Output: 3 4 3 6 2 */