#include <iostream> #include <vector> #include <deque> using namespace std; vector <int> roots; int n, m, t, x, y; int indexRoot; void read(){ cin >> n >> m; int a, b; roots.resize(n+1, 0); for(int i = 0; i < n-1; i++){ cin >> a >> b; if (b < a) roots[a] = b; else roots[b] = a; } } deque <int> getPath(int index){ deque <int> v; v.push_front(index); while (index){ v.push_front(roots[index]); index = roots[index]; } v.pop_front();//this shouldn't matter return v; } void change(int index, int ancestor){ int oldAncestor = roots[index]; roots[index] = ancestor; if(oldAncestor != 0){ change(oldAncestor, index); } } int getLCA(deque <int> dq1, deque <int> dq2){ int index = 0; while(dq1.front() == dq2.front()){ index = dq1.front(); dq1.pop_front(); dq2.pop_front(); } return index; } void conflict(int a, int b){ int boss = getLCA(getPath(a), getPath(b)); if(boss == a || boss == b) cout << -1 << "\n"; else cout << boss << "\n"; } int main() { read(); for(int i = 0; i < m; i++){ cin >> t >> x; if(t == 1){ indexRoot = x; } else{ cin >> y; change(indexRoot,0); conflict(x, y); } } }