#include <bits/stdc++.h>
using namespace std;
template <class T>
int chkmax(T &a, T b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
int chkmin(T &a, T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class iterator>
void output(iterator begin, iterator end, ostream &out = cerr) {
  while (begin != end) {
    out << (*begin) << " ";
    begin++;
  }
  out << endl;
}
template <class T>
void output(T x, ostream &out = cerr) {
  output(x.begin(), x.end(), out);
}
void fast_io() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
struct fenwick {
  vector<int> t;
  int n;
  fenwick() {}
  void init(int _n) {
    n = _n;
    t.resize(n);
  }
  void update(int pos, int val) {
    while (pos < n) {
      t[pos] += val;
      pos = (pos | (pos + 1));
    }
  }
  int get(int r) {
    int res = 0;
    while (r >= 0) {
      res += t[r];
      r = (r & (r + 1)) - 1;
    }
    return res;
  }
  int get(int l, int r) { return get(r) - get(l - 1); }
  int operator[](int pos) { return get(pos, pos); }
};
struct segment {
  int l, r, clr;
  segment(int _l, int _r, int _clr) : l(_l), r(_r), clr(_clr) {}
};
bool operator<(segment a, segment b) { return a.l < b.l; }
const int INF = 1e9;
const int mx = 2e5 + 228;
const int lg = 20;
int n, q, timer, ptr;
int sz[mx], tin[mx], tout[mx], h[mx], euler[mx], par[mx], p[2 * mx], _p[2 * mx],
    link[mx], up[mx][lg];
vector<int> g[mx], children[mx];
set<segment> s;
fenwick f, f0;
int pos[mx], deg[mx];
void build_order() {
  set<pair<int, int> > burn;
  for (int i = 0; i < n; ++i) {
    deg[i] = g[i].size();
    pos[i] = -1;
    if (deg[i] == 1) {
      burn.insert({p[i], i});
    }
  }
  for (int i = 0; i < n; ++i) {
    int v = burn.begin()->second;
    burn.erase(burn.begin());
    pos[v] = i;
    for (auto v1 : g[v]) {
      deg[v1]--;
      if (deg[v1] == 1) {
        burn.insert({p[v1], v1});
      }
    }
  }
}
int upper(int u, int v) { return (tin[u] <= tin[v] && tout[v] <= tout[u]); }
int lca(int u, int v) {
  if (upper(u, v)) return u;
  if (upper(v, u)) return v;
  for (int i = lg - 1; i >= 0; --i) {
    if (!upper(up[u][i], v)) {
      u = up[u][i];
    }
  }
  return up[u][0];
}
int distance(int u, int v) { return h[u] + h[v] - 2 * h[lca(u, v)]; }
void update_way(int high, int low, int include, vector<pair<int, int> > &res) {
  while (true) {
    if (low == high && !include) {
      break;
    }
    int tlow = tin[low];
    if (upper(link[tlow], high)) {
      if (include) {
        res.push_back({tin[high], tlow});
      } else {
        res.push_back({tin[high] + 1, tlow});
      }
      break;
    }
    res.push_back({tin[link[tlow]], tlow});
    low = par[link[tlow]];
  }
}
vector<pair<int, int> > get_way(int u, int v) {
  vector<pair<int, int> > res;
  int e = lca(u, v);
  update_way(e, u, 1, res);
  update_way(e, v, 0, res);
  return res;
}
void seg_update_color(int l, int r, int clr_id) {
  while (true) {
    auto seg = *prev(s.upper_bound({r, INF, INF}));
    s.erase(seg);
    f.update(seg.clr, -(seg.r - seg.l + 1));
    if (seg.clr == 0) {
      int L = max(l, seg.l), R = min(r, seg.r);
      for (int i = L; i <= R; ++i) {
        f0.update(pos[euler[i]], -1);
      }
    }
    if (seg.r > r) {
      s.insert({r + 1, seg.r, seg.clr});
      f.update(seg.clr, seg.r - r);
    }
    if (seg.l < l) {
      s.insert({seg.l, l - 1, seg.clr});
      f.update(seg.clr, l - seg.l);
    }
    if (seg.l <= l) {
      break;
    }
  }
  s.insert({l, r, clr_id});
  f.update(clr_id, r - l + 1);
}
void update_color(int u, int v, int clr_id) {
  vector<pair<int, int> > segs = get_way(u, v);
  for (auto pp : segs) {
    seg_update_color(pp.first, pp.second, clr_id);
  }
}
void up_query(int v) {
  int u = _p[ptr - 1];
  update_color(u, v, ptr - 1);
  update_color(v, v, ptr);
  p[v] = ptr;
  _p[ptr] = v;
  ptr++;
}
int when_query(int v) {
  int clr = prev(s.upper_bound({tin[v], INF, INF}))->clr;
  int res = f.get(clr - 1);
  if (clr != 0) {
    res += distance(v, _p[clr]);
  } else {
    res += f0.get(pos[v] - 1);
  }
  return res;
}
int compare_query(int u, int v) {
  if (when_query(u) < when_query(v)) {
    return u;
  } else {
    return v;
  }
}
void build_hld() {
  f.init(n + q + 1);
  f0.init(n);
  int cur_link = 0;
  for (int i = 1; i < n; ++i) {
    if (children[par[euler[i]]][0] != euler[i]) {
      cur_link = euler[i];
    }
    link[i] = cur_link;
  }
  for (int i = 0; i < n; ++i) {
    f0.update(i, 1);
  }
  s.insert({0, n - 1, 0});
  f.update(0, n);
}
void hang(int v, int pv) {
  par[v] = pv;
  sz[v] = 1;
  vector<pair<int, int> > vp;
  int id = 0;
  for (auto v1 : g[v]) {
    if (v1 != pv) {
      children[v].push_back(v1);
      hang(v1, v);
      vp.push_back({sz[v1], id++});
      sz[v] += sz[v1];
    }
  }
  if (!vp.empty()) {
    int id = max_element(vp.begin(), vp.end()) - vp.begin();
    swap(children[v][0], children[v][id]);
  }
}
void timer_dfs(int v) {
  up[v][0] = par[v];
  for (int i = 1; i < lg; ++i) {
    up[v][i] = up[up[v][i - 1]][i - 1];
  }
  tin[v] = timer++;
  euler[tin[v]] = v;
  for (auto v1 : children[v]) {
    h[v1] = h[v] + 1;
    timer_dfs(v1);
  }
  tout[v] = timer - 1;
}
void read_tree() {
  cin >> n >> q;
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
}
void fill_p() {
  iota(p, p + n, 0);
  iota(_p, _p + n, 0);
  ptr = n;
}
void process_queries() {
  for (int i = 0; i < q; ++i) {
    string type;
    cin >> type;
    int v, u;
    if (type == "up") {
      cin >> v;
      v--;
      up_query(v);
    }
    if (type == "when") {
      cin >> v;
      v--;
      cout << when_query(v) + 1 << '\n';
    }
    if (type == "compare") {
      cin >> u >> v;
      u--;
      v--;
      cout << compare_query(u, v) + 1 << '\n';
    }
  }
}
signed main() {
  fast_io();
  read_tree();
  hang(0, 0);
  timer_dfs(0);
  fill_p();
  build_hld();
  build_order();
  process_queries();
}

### Prompt

Construct a CPP code solution to the problem outlined:

Lena is playing with matches. The natural question arising in the head of any child playing with matches is whether it's possible to set a tree on fire with a matches, or not.

Let's say, that the tree is a connected graph without cycles and the vertices are labeled with integers 1, 2, …, n. Also every vertex v has some integer priority p_v associated with it. All priorities are distinct.

It turns out, that if you set a tree on fire, it will burn to nothing. However, this process doesn't happen instantly. At the beginning, burns out the leaf (a vertex is called to be a leaf if it has only one adjacent vertex) of the tree of the minimum priority. Then burns out the leaf of the minimal priority of the remaining tree, and so on. This way, the vertices turn into the leaves and burn out until only one vertex remains. Then this vertex burns out as well.

Lena has prepared a tree of n vertices and every vertex in it has a priority p_v = v. Lena is very curious about burning out this tree. However, she understands, that if she will burn the tree now, then it will disappear completely. Lena is a kind girl and she will feel bad for the burned tree, so she wants to study the process of burning the tree only in her mind. Lena wants to process q queries, each of them is one of three following types:

  * "up v", assign the vertex v priority 1 + max\\{p_1, p_2, …, p_n\}; 
  * "when v", find the step at which the vertex v will burn out, if the tree would be set on fire now; 
  * "compare v u", find out which of the vertices v and u will burn out first, if the tree would be set on fire now. 



Notice, that if all priorities would be distinct, then after the "up" query they will stay distinct as well. Initially all priorities are distinct, hence during any (purely hypothetical of course) burning of the tree, all leafs would have distinct priorities.

Input

The first line contains two integers n and q (2 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — the number of vertices in the tree and the number of queries.

The i-th of the following n - 1 lines contains two integers v_i, u_i (1 ≤ v_i, u_i ≤ n), denoting the endpoints of the i-th edge.

Each of the remaining q lines contains a query of one of the following three types:

  * "up v" (1 ≤ v ≤ n) — change the priority of vertex v; 
  * "when v" (1 ≤ v ≤ n) — determine the step at which the vertex v will burn out; 
  * "compare v u" (1 ≤ v, u ≤ n, v ≠ u) — determine which of vertices v and u will burn out earlier in the current tree. 



It's guaranteed, that there is at least one query of type "when" or "compare".

Output

For every query of type "when" print one integer in range from 1 to n — the step at which the vertex v will burn out.

For every query of type "compare" print either v or u, depending on which one will burn out earlier.

Examples

Input


5 7
1 5
1 2
1 3
4 3
when 1
when 2
when 3
when 4
when 5
compare 2 3
compare 3 4


Output


4
1
3
2
5
2
4


Input


5 5
1 5
1 2
1 3
4 3
up 1
compare 2 4
compare 4 3
compare 3 1
compare 1 5


Output


2
4
3
5

Note

In the first example, the process of burning of the tree is illustrated on the following picture:

<image>

In particular, the vertices of the tree will burn out in the following order: [2, 4, 3, 1, 5].

In the second example, after applying the "up" operation, the order of vertices will change to: [2, 4, 3, 5, 1].

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
int chkmax(T &a, T b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
int chkmin(T &a, T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class iterator>
void output(iterator begin, iterator end, ostream &out = cerr) {
  while (begin != end) {
    out << (*begin) << " ";
    begin++;
  }
  out << endl;
}
template <class T>
void output(T x, ostream &out = cerr) {
  output(x.begin(), x.end(), out);
}
void fast_io() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
struct fenwick {
  vector<int> t;
  int n;
  fenwick() {}
  void init(int _n) {
    n = _n;
    t.resize(n);
  }
  void update(int pos, int val) {
    while (pos < n) {
      t[pos] += val;
      pos = (pos | (pos + 1));
    }
  }
  int get(int r) {
    int res = 0;
    while (r >= 0) {
      res += t[r];
      r = (r & (r + 1)) - 1;
    }
    return res;
  }
  int get(int l, int r) { return get(r) - get(l - 1); }
  int operator[](int pos) { return get(pos, pos); }
};
struct segment {
  int l, r, clr;
  segment(int _l, int _r, int _clr) : l(_l), r(_r), clr(_clr) {}
};
bool operator<(segment a, segment b) { return a.l < b.l; }
const int INF = 1e9;
const int mx = 2e5 + 228;
const int lg = 20;
int n, q, timer, ptr;
int sz[mx], tin[mx], tout[mx], h[mx], euler[mx], par[mx], p[2 * mx], _p[2 * mx],
    link[mx], up[mx][lg];
vector<int> g[mx], children[mx];
set<segment> s;
fenwick f, f0;
int pos[mx], deg[mx];
void build_order() {
  set<pair<int, int> > burn;
  for (int i = 0; i < n; ++i) {
    deg[i] = g[i].size();
    pos[i] = -1;
    if (deg[i] == 1) {
      burn.insert({p[i], i});
    }
  }
  for (int i = 0; i < n; ++i) {
    int v = burn.begin()->second;
    burn.erase(burn.begin());
    pos[v] = i;
    for (auto v1 : g[v]) {
      deg[v1]--;
      if (deg[v1] == 1) {
        burn.insert({p[v1], v1});
      }
    }
  }
}
int upper(int u, int v) { return (tin[u] <= tin[v] && tout[v] <= tout[u]); }
int lca(int u, int v) {
  if (upper(u, v)) return u;
  if (upper(v, u)) return v;
  for (int i = lg - 1; i >= 0; --i) {
    if (!upper(up[u][i], v)) {
      u = up[u][i];
    }
  }
  return up[u][0];
}
int distance(int u, int v) { return h[u] + h[v] - 2 * h[lca(u, v)]; }
void update_way(int high, int low, int include, vector<pair<int, int> > &res) {
  while (true) {
    if (low == high && !include) {
      break;
    }
    int tlow = tin[low];
    if (upper(link[tlow], high)) {
      if (include) {
        res.push_back({tin[high], tlow});
      } else {
        res.push_back({tin[high] + 1, tlow});
      }
      break;
    }
    res.push_back({tin[link[tlow]], tlow});
    low = par[link[tlow]];
  }
}
vector<pair<int, int> > get_way(int u, int v) {
  vector<pair<int, int> > res;
  int e = lca(u, v);
  update_way(e, u, 1, res);
  update_way(e, v, 0, res);
  return res;
}
void seg_update_color(int l, int r, int clr_id) {
  while (true) {
    auto seg = *prev(s.upper_bound({r, INF, INF}));
    s.erase(seg);
    f.update(seg.clr, -(seg.r - seg.l + 1));
    if (seg.clr == 0) {
      int L = max(l, seg.l), R = min(r, seg.r);
      for (int i = L; i <= R; ++i) {
        f0.update(pos[euler[i]], -1);
      }
    }
    if (seg.r > r) {
      s.insert({r + 1, seg.r, seg.clr});
      f.update(seg.clr, seg.r - r);
    }
    if (seg.l < l) {
      s.insert({seg.l, l - 1, seg.clr});
      f.update(seg.clr, l - seg.l);
    }
    if (seg.l <= l) {
      break;
    }
  }
  s.insert({l, r, clr_id});
  f.update(clr_id, r - l + 1);
}
void update_color(int u, int v, int clr_id) {
  vector<pair<int, int> > segs = get_way(u, v);
  for (auto pp : segs) {
    seg_update_color(pp.first, pp.second, clr_id);
  }
}
void up_query(int v) {
  int u = _p[ptr - 1];
  update_color(u, v, ptr - 1);
  update_color(v, v, ptr);
  p[v] = ptr;
  _p[ptr] = v;
  ptr++;
}
int when_query(int v) {
  int clr = prev(s.upper_bound({tin[v], INF, INF}))->clr;
  int res = f.get(clr - 1);
  if (clr != 0) {
    res += distance(v, _p[clr]);
  } else {
    res += f0.get(pos[v] - 1);
  }
  return res;
}
int compare_query(int u, int v) {
  if (when_query(u) < when_query(v)) {
    return u;
  } else {
    return v;
  }
}
void build_hld() {
  f.init(n + q + 1);
  f0.init(n);
  int cur_link = 0;
  for (int i = 1; i < n; ++i) {
    if (children[par[euler[i]]][0] != euler[i]) {
      cur_link = euler[i];
    }
    link[i] = cur_link;
  }
  for (int i = 0; i < n; ++i) {
    f0.update(i, 1);
  }
  s.insert({0, n - 1, 0});
  f.update(0, n);
}
void hang(int v, int pv) {
  par[v] = pv;
  sz[v] = 1;
  vector<pair<int, int> > vp;
  int id = 0;
  for (auto v1 : g[v]) {
    if (v1 != pv) {
      children[v].push_back(v1);
      hang(v1, v);
      vp.push_back({sz[v1], id++});
      sz[v] += sz[v1];
    }
  }
  if (!vp.empty()) {
    int id = max_element(vp.begin(), vp.end()) - vp.begin();
    swap(children[v][0], children[v][id]);
  }
}
void timer_dfs(int v) {
  up[v][0] = par[v];
  for (int i = 1; i < lg; ++i) {
    up[v][i] = up[up[v][i - 1]][i - 1];
  }
  tin[v] = timer++;
  euler[tin[v]] = v;
  for (auto v1 : children[v]) {
    h[v1] = h[v] + 1;
    timer_dfs(v1);
  }
  tout[v] = timer - 1;
}
void read_tree() {
  cin >> n >> q;
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
}
void fill_p() {
  iota(p, p + n, 0);
  iota(_p, _p + n, 0);
  ptr = n;
}
void process_queries() {
  for (int i = 0; i < q; ++i) {
    string type;
    cin >> type;
    int v, u;
    if (type == "up") {
      cin >> v;
      v--;
      up_query(v);
    }
    if (type == "when") {
      cin >> v;
      v--;
      cout << when_query(v) + 1 << '\n';
    }
    if (type == "compare") {
      cin >> u >> v;
      u--;
      v--;
      cout << compare_query(u, v) + 1 << '\n';
    }
  }
}
signed main() {
  fast_io();
  read_tree();
  hang(0, 0);
  timer_dfs(0);
  fill_p();
  build_hld();
  build_order();
  process_queries();
}

```