The year is 2025. In the past decade, Xorin's efforts genuinely payed off, especially considering that he and Xoranna are now happily married. Furthermore, our dear friend is now a successful employee at a Fortune 500 company.

As terrific as he may be at his job, Xorin still requires Xoranna's help. She agreed to help him intervene and settle any conflicts that may arise between the company's employees.

The internal hierarchy can be considered an undirected tree. The CEO may change at any moment, meaning that the tree suffers a re-rooting. Therefore, Xoranna must be able to face two kinds of events:

**change(x)**- employee**x**becomes the CEO**conflict(x, y)**- a conflict arises between employees**x**and**y**

Xoranna has already prepared for these situations. Whenever two employees get in a conflict, she delegates their closest common boss to address the issue. If any of the employees involved is the other's boss (direct or indirect), Xoranna will personally step in and solve their problem. Your task is to help Xoranna decide whom to assign to each matter.

# Input

The first line of the input contains two integers **n** and **m**, representing the number of employees and the number of tasks, respectively.

The following **n-1** lines contain the hierarchy's edges, in no particular order.

The following **m** lines contain the events, structured in the following manner:

**1 x**- describing a**change(x)**event**2 x y**- describing a**conflict(x, y)**event

# Output

You should output one line for each **conflict** in the given input. The answer should be either the employee that will have to solve the issue, or **-1**, in case Xoranna personally steps in.

# Constraints

- 1 ≤ n, m ≤ 10
^{5} - Initially, employee number
**1**is the CEO of the company. - No employee has multiple personality disorder, so one cannot encounter a conflict with himself.

# Sample

Input | Output |
---|---|

11 11 1 2 3 1 4 2 5 2 6 2 7 4 8 4 9 6 10 3 11 3 2 10 11 2 8 9 2 5 11 2 5 6 2 4 2 1 3 2 1 10 2 4 6 2 9 1 1 4 2 9 10 | 3 2 1 2 -1 3 2 -1 2 |

**Bosses** can be summarised as follows:

Given a root-adjustable tree, find the Lowest Common Ancestor between pairs of given nodes.

At a closer look, we notice that any LCA can be obtained solely by using the original tree. Regardless of current root, only 4 LCAs are needed:

- lca
_{1}= LCA(x, y) - lca
_{2}= LCA(x, currentRoot) - lca
_{3}= LCA(y, currentRoot) - lca
_{4}= root

For each query, the solution is the **lca** that grants the minimum value for the expression:

dist(lca_{i}, x) + dist(lca_{i}, y), 1 ≤ i ≤ 4

## C++ solution Cosmin Rusu

1 #include <vector> 2 #include <iostream> 3 4 using namespace std; 5 6 const int maxn = 100005; 7 const int maxlg = 20; 8 9 vector <int> g[maxn]; 10 int n, m, root = 1, rmq[maxlg][maxn << 1], euler[maxn << 1], level[maxn << 1], k, first[maxn], lg[maxn << 1]; 11 12 inline void dfs(int node, int father, int actlevel) { 13 euler[++ k] = node; 14 level[ k ] = actlevel; 15 first[node] = k; 16 for(vector <int> :: iterator it = g[node].begin() ; it != g[node].end() ; ++ it) { 17 if(*it == father) 18 continue; 19 dfs(*it, node, actlevel + 1); 20 euler[++ k] = node; 21 level[ k ] = actlevel; 22 } 23 } 24 25 inline void preprocess() { 26 for(int i = 2 ; i <= k ; ++ i) 27 lg[i] = lg[i >> 1] + 1; 28 for(int i = 1 ; i <= k ; ++ i) 29 rmq[0][i] = i; 30 for(int l = 1 ; (1 << l) <= k ; ++ l) { 31 int aux = (1 << (l - 1)); 32 for(int i = 1 ; i + (1 << l) - 1 <= k ; ++ i) { 33 rmq[l][i] = rmq[l - 1][i]; 34 if(level[rmq[l][i]] > level[rmq[l - 1][i + aux]]) 35 rmq[l][i] = rmq[l - 1][i + aux]; 36 } 37 } 38 } 39 40 inline int LCA(int x, int y) { 41 x = first[x]; 42 y = first[y]; 43 if(x > y) 44 swap(x, y); 45 int logaritm = lg[y - x + 1]; 46 int ret = rmq[logaritm][x]; 47 if(level[ret] > level[rmq[logaritm][y - (1 << logaritm) + 1]]) 48 ret = rmq[logaritm][y - (1 << logaritm) + 1]; 49 return euler[ret]; 50 } 51 52 inline int dist(int x, int y) { 53 int lca = LCA(x, y); 54 return level[first[x]] + level[first[y]] - 2 * level[first[lca]]; 55 } 56 57 inline int check(int x, int y, int lca) { 58 return dist(x, lca) + dist(y, lca) + 2 * dist(lca, root); 59 } 60 61 inline int query(int x, int y) { 62 int lca = LCA(x, y); 63 int auxlca = LCA(x, root); 64 if(check(x, y, lca) > check(x, y, auxlca)) 65 lca = auxlca; 66 auxlca = LCA(y, root); 67 if(check(x, y, lca) > check(x, y, auxlca)) 68 lca = auxlca; 69 auxlca = root; 70 if(check(x, y, lca) > check(x, y, auxlca)) 71 lca = auxlca; 72 return lca; 73 } 74 75 int main() { 76 cin >> n >> m; 77 for(int i = 1 ; i < n ; ++ i) { 78 int x, y; 79 cin >> x >> y; 80 g[x].push_back(y); 81 g[y].push_back(x); 82 } 83 dfs(1, 0, 1); 84 preprocess(); 85 for(int i = 1 ; i <= m ; ++ i) { 86 int type, x, y; 87 cin >> type; 88 if(type == 1) { 89 cin >> x; 90 root = x; 91 } 92 else { 93 cin >> x >> y; 94 int lca = query(x, y); 95 if(lca == x || lca == y) 96 cout << "-1\n"; 97 else 98 cout << lca << '\n'; 99 } 100 } 101 }