#include <iostream> #include <vector> #include <cstdio> #include <cstring> using namespace std; const int SIZE = 2e5+5; int n, m, x[SIZE], y[SIZE]; int opt[SIZE], a[SIZE], b[SIZE], c[SIZE], d[SIZE]; int id(int x, int y) { return (x - 1) * n + y; } namespace o1 { const int SIZE = 105; int q[SIZE * SIZE], head, tail; vector<int> g[SIZE * SIZE]; int fx[] = {-1, 0, 1, 0}, fy[] = {0, 1, 0, -1}; int dis[SIZE*SIZE][SIZE*SIZE]; void bfs(int st) { head = tail = 0; q[++tail] = st; dis[st][st] = 0; while (head < tail) { ++head; int u = q[head]; for (const int v : g[u]) { if (dis[st][v] == -1) { dis[st][v] = dis[st][u] + 1; q[++tail] = v; } } } } int main() { memset(dis, -1, sizeof(dis)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (i < j) { if (i > 1) g[id(i, j)].push_back(id(i - 1, j)); if (i < n) g[id(i, j)].push_back(id(i + 1, j)); } else if (i > j) { if (j > 1) g[id(i, j)].push_back(id(i, j - 1)); if (j < n) g[id(i, j)].push_back(id(i, j + 1)); } else { if (i > 1) g[id(i, j)].push_back(id(i - 1, j)); if (1 < j) g[id(i, j)].push_back(id(i, j - 1)); } } } for (int i = 1; i < n; ++i) { g[id(i, x[i])].push_back(id(i + 1, x[i])); g[id(i + 1, x[i])].push_back(id(i, x[i])); g[id(y[i], i)].push_back(id(y[i], i + 1)); g[id(y[i], i + 1)].push_back(id(y[i], i)); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { bfs(id(i, j)); } } for (int o = 1; o <= m; ++o) { printf("%d\n",dis[id(a[o],b[o])][id(c[o], d[o])]); } return 0; } } int main() { #ifdef fio freopen("../test.in","r",stdin); #endif cin >> n >> m; for (int i = 1; i < n; ++i) { scanf("%d%d",x+i,y+i); } bool fga = true; for (int i = 1; i <= m; ++i) { scanf("%d",opt+i); if (opt[i] == 1) { fga = false; scanf("%d%d%d",a+i,b+i,c+i); } else { scanf("%d%d%d%d",a+i,b+i,c+i,d+i); } } if (fga) { if (n <= 100 && m <= 2e5) return o1::main(); } else { } return 0; }