#include <iostream> #include <vector> using namespace std; vector<int> a; vector<int> lcas; const int N = 2e5 + 5; const int LOG = 25; int m; vector<int> adj[N]; int up[N][LOG]; int dept[N]; void dfs(int node, int parent) { for (auto i : adj[node]) { if (i == parent) continue; up[i][0] = node; for (int j = 1;j < LOG;++j) { up[i][j] = up[up[i][j - 1]][j - 1]; } dept[i] = dept[node] + 1; dfs(i, node); } } int lift(int a, int k) { for (int j = LOG - 1;j >= 0;--j) { if (k & (1 << j)) { a = up[a][j]; } } return a; } int lca(int a, int b) { if (a == b) return a; if (dept[a] < dept[b]) { swap(a, b); } int dif = dept[a] - dept[b]; a = lift(a, dif); if (a == b) return a; for (int j = LOG - 1;j >= 0;--j) { if (up[a][j] != up[b][j]) { a = up[a][j]; b = up[b][j]; } } return up[a][0]; } //struct segtree //{ // long long sz = 1; // void init() // { // while (sz < m) // { // sz *= 2; // } // lcas.assign(2 * sz - 1, 0 * 1ll); // } // void build(long long x, long long lx, long long rx) // { // if (rx - lx == 1) // { // if (lx < a.size() * 1ll) // { // lcas[x] = a[lx]; // } // return; // } // long long mid = (lx + rx) / 2; // build(2 * x + 1, lx, mid); // build(2 * x + 2, mid, rx); // lcas[x] = lca(lcas[2 * x + 1], lcas[2 * x + 2]); // } // void build() // { // build(0, 0, sz); // } // void set(long long ind, long long v, long long x, long long lx, long long rx) // { // if (rx - lx == 1) // { // lcas[x] = v; // return; // } // long long mid = (lx + rx) / 2; // if (ind < mid) // { // set(ind, v, 2 * x + 1, lx, mid); // } // else // { // set(ind, v, 2 * x + 2, mid, rx); // } // lcas[x] = lca(lcas[2 * x + 1], lcas[2 * x + 2]); // } // void set(long long ind, long long v) // { // set(ind, v, 0, 0, sz); // } // long long seglca(long long l, long long r, long long x, long long lx, long long rx) // { // if (lx >= r || rx <= l) // { // return 0; // } // if (lx >= l && rx <= r) // { // return lcas[x]; // } // long long mid = (lx + rx) / 2; // long long llca = seglca(l, r, 2 * x + 1, lx, mid); // long long rlca = seglca(l, r, 2 * x + 2, mid, rx); // return lca(llca, rlca); // } // long long seglca(long long l, long long r) // { // return seglca(l, r, 0, 0, sz); // } //}; int main() { /* segtree st;*/ int n, q; cin >> n >>m>> q; for (int i = 0;i < n - 1;++i) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } dept[1] = 0; dfs(1, 0); for (int i = 0;i < m;++i) { int x; cin >> x; a.push_back(x); } //st.init(); //st.build(); for (int i = 0;i < q;++i) { int type; cin >> type; if (type == 1) { int ind, v; cin >> ind >> v; ind--; a[ind] = v; } else if (type == 2) { int l, r, v; cin >> l >> r >> v; --l; --r; bool flag = false; for (int j = l;j < r;++j) { if (lca(a[j], a[j + 1]) == v) { cout << j + 1 << " " << j + 2 << endl; flag = true; break; } if (a[j] == v) { cout << j + 1 << " " << j + 1 << endl; flag = true; break; } } if (a[r] == v) { cout << r + 1 << " " << r + 1 << endl; flag = true; } if (!flag) { cout << -1 << " " << -1 << endl; } } } }