#include<bits/stdc++.h> using namespace std; #ifdef IAKIOI #define cin fin ifstream cin("in.txt"); #endif #define ll long long using pii = pair<int,int>; int n, m; constexpr int N = 2e5 + 5; int x[N], y[N], vis[2000000]; vector<int>e[2000000]; inline int h(int i, int j) { return (i) * (n + 1) + j; } inline void add(int u, int v) { e[u].emplace_back(v); e[v].emplace_back(u); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 1; i < n; ++i) { cin >> x[i] >> y[i]; } while (m--) { int op, a, b, c, d; cin >> op >> a >> b >> c; if (op == 1) { x[a] = b, y[a] = c; } else { cin >> d; for (int i = 0; i <= n + 1; ++i) for (int j = 0; j <= n + 1; ++j) e[h(i, j)].clear(); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) { if (max(i, j) == max(i, j - 1)) add(h(i ,j), h(i, j - 1)); if (max(i, j) == max(i, j + 1)) add(h(i ,j), h(i, j + 1)); if (max(i, j) == max(i - 1, j)) add(h(i ,j), h(i - 1, j)); if (max(i, j) == max(i + 1, j)) add(h(i ,j), h(i + 1, j)); } for (int i = 1; i < n; ++i) { add(h(i, x[i]), h(i + 1, x[i])); add(h(y[i], i), h(y[i], i + 1)); } // for (int x : e[h(3, 4)])cerr << x / (n + 1) << ' ' << x % (n + 1) << '\n'; queue<pii>q; q.emplace(h(a, b), 0); vis[h(a, b)] = 1; while (!q.empty()) { int x = q.front().first, s = q.front().second; // cerr << x / (n + 1) << ' ' << x % (n + 1) << ' ' << s << '\n'; q.pop(); if (x == h(c, d)) { cout << s << endl; return 0; } for (int v : e[x]) { if (!vis[v]) vis[v] = 1, q.emplace(v, s + 1); } } } } return 0; }