#include <bits/stdc++.h> #define NMAX 200001 #define LOG 20 using namespace std; int n, m, q; vector<int> muchii[NMAX]; ///muchiile arborelui int nivel[NMAX]; ///nivelul fiecarui nod int stra[LOG][NMAX]; ///stra[e][i] = al e-lea stramos al nodului i void dfs(int nod, int tata) ///salvam tatal fiecarui nod { stra[0][nod]=tata; nivel[nod]=1+nivel[tata]; for(auto& fiu : muchii[nod]) { if(fiu!=tata) dfs(fiu, nod); } } void precalc() ///precalculam structura de date stra { for(int e=1; e<LOG; e++) { for(int i=1; i<=n; i++) stra[e][i]=stra[e-1][stra[e-1][i]]; } } int up(int nod, int k) ///al k-lea stramos al lui nod { for(int e=LOG-1; e>=0; e--) { if((1<<e)<=k) { nod=stra[e][nod]; k-=(1<<e); } } return nod; } int LCA(int nod1, int nod2) ///LCA-ul a doua noduri { if(nivel[nod1]<nivel[nod2]) swap(nod1, nod2); if(nod2==0) return nod1; nod1=up(nod1, nivel[nod1]-nivel[nod2]); ///il aducem pe nod1 la nivelul nodului nod2 if(nod1==nod2) return nod1; for(int e=LOG-1; e>=0; e--) ///cautam binar ultimul stramos al fiecarui nod care nu este comun { if(stra[e][nod1]!=stra[e][nod2]) { nod1=stra[e][nod1]; nod2=stra[e][nod2]; } } return stra[0][nod1]; } int a[NMAX]; int lca_a[NMAX]; ///LCA-ul a doua numere situate pe pozitii consecutive in a set<int> pozitii_a[NMAX]; ///pozitiile pe care se afla fiecare valoare in a set<int> pozitii_lca[NMAX]; ///pozitiile pe care se afla fiecare valoare in lca_a int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> q; for(int i=1; i<=n-1; i++) { int u, v; cin >> u >> v; muchii[u].push_back(v); muchii[v].push_back(u); } dfs(1, 0); precalc(); for(int i=1; i<=m; i++) { cin >> a[i]; pozitii_a[a[i]].insert(i); } for(int i=1; i<=m; i++) { ///daca exista un interval in [l, r] care are LCA-ul v, atunci fie exista doua pozitii consecutive cu LCA-ul v, fie v se afla in interval ///astfel, avem nevoie doar de LCA-ul numerelor aflate pe pozitii consecutive lca_a[i]=LCA(a[i], a[i+1]); pozitii_lca[lca_a[i]].insert(i); } while(q--) { int tip; cin >> tip; if(tip==1) { int pos, v; cin >> pos >> v; pozitii_a[a[pos]].erase(pos); if(pos>1) pozitii_lca[lca_a[pos-1]].erase(pos-1); pozitii_lca[lca_a[pos]].erase(pos); a[pos]=v; if(pos>1) lca_a[pos-1]=LCA(a[pos-1], a[pos]); lca_a[pos]=LCA(a[pos], a[pos+1]); pozitii_a[a[pos]].insert(pos); if(pos>1) pozitii_lca[lca_a[pos-1]].insert(pos-1); pozitii_lca[lca_a[pos]].insert(pos); } else { int l, r, v; cin >> l >> r >> v; if(pozitii_a[v].lower_bound(l)!=pozitii_a[v].end() && (*pozitii_a[v].lower_bound(l))<=r) ///cautam prima pozitie a lui v situata dupa l; daca aceasta este mai mica sau egala cu r, atunci luam intervalul [x, x] { int x=(*pozitii_a[v].lower_bound(l)); cout << x << " " << x << "\n"; } else if(pozitii_lca[v].lower_bound(l)!=pozitii_lca[v].end() && (*pozitii_lca[v].lower_bound(l))<=r-1) ///cautam prima pozitie a lui v ca LCA situata dupa l; daca aceasta este mai mica sau egala cu r-1, atunci luam intervalul [x, x+1] { int x=(*pozitii_lca[v].lower_bound(l)); cout << x << " " << x+1 << "\n"; } else { cout << -1 << " " << -1 << "\n"; } } } return 0; }