Xenia the programmer has a tree consisting of n nodes. We will consider the tree nodes indexed from 1 to n. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue.

The distance between two tree nodes v and u is the number of edges in the shortest path between v and u.

Xenia needs to learn how to quickly execute queries of two types:

  1. paint a specified blue node in red; 
  2. calculate which red node is the closest to the given one and print the shortest distance to the closest red node. 



Your task is to write a program which will execute the described queries.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of nodes in the tree and the number of queries. Next n - 1 lines contain the tree edges, the i-th line contains a pair of integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — an edge of the tree.

Next m lines contain queries. Each query is specified as a pair of integers ti, vi (1 ≤ ti ≤ 2, 1 ≤ vi ≤ n). If ti = 1, then as a reply to the query we need to paint a blue node vi in red. If ti = 2, then we should reply to the query by printing the shortest distance from some red node to node vi.

It is guaranteed that the given graph is a tree and that all queries are correct.

Output

For each second type query print the reply in a single line.

Examples

Input

5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5


Output

0
3
2
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 2;
const int LOG = 17;
const int inf = 1e9;
int jump[LOG][maxn];
int depth[maxn];
bool red[maxn];
int tin[maxn];
int tout[maxn];
int tmr = 0;
int dist[maxn];
int nearest[maxn];
queue<int> q;
vector<int> e[maxn];
vector<int> New;
int n;
void dfs(int v, int id, int p, int h) {
  if (id == 0)
    jump[id][v] = p;
  else
    jump[id][v] = jump[id - 1][jump[id - 1][v]];
  depth[v] = h;
  for (int i = 0; i < (int)e[v].size(); i++)
    if (e[v][i] != p) dfs(e[v][i], id, v, h + 1);
}
void dfsT(int v, int p) {
  tin[v] = tmr++;
  for (int i = 0; i < (int)e[v].size(); i++)
    if (e[v][i] != p) dfsT(e[v][i], v);
  tout[v] = tmr++;
}
inline bool pred(int v, int u) {
  return tin[v] <= tin[u] && tout[u] <= tout[v];
}
inline int lca(int v, int u) {
  if (pred(v, u)) return v;
  if (pred(u, v)) return u;
  for (int i = LOG - 1; i >= 0; i--)
    if (!pred(jump[i][v], u)) v = jump[i][v];
  return jump[0][v];
}
inline int len(int v, int u) {
  int z = lca(v, u);
  return (depth[v] - depth[z]) + (depth[u] - depth[z]);
}
void re_build() {
  int v;
  for (int i = 0; i < (int)New.size(); i++) red[New[i]] = 1;
  New.clear();
  memset(dist, 63, sizeof(dist));
  for (int i = 0; i < n; i++)
    if (red[i]) {
      dist[i] = 0;
      q.push(i);
    }
  while (!q.empty()) {
    v = q.front();
    q.pop();
    for (int i = 0; i < (int)e[v].size(); i++)
      if (dist[e[v][i]] > dist[v] + 1) {
        dist[e[v][i]] = dist[v] + 1;
        q.push(e[v][i]);
      }
  }
}
int main() {
  int m, m_sqrt, v, u, ans, t;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n - 1; i++) {
    scanf("%d%d", &v, &u);
    v--;
    u--;
    e[v].push_back(u);
    e[u].push_back(v);
  }
  for (int i = 0; i < LOG; i++) dfs(0, i, 0, 0);
  dfsT(0, -1);
  m_sqrt = sqrt(m * log(n));
  if (m_sqrt == 0) m_sqrt++;
  red[0] = 1;
  re_build();
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &t, &v);
    v--;
    if (i % m_sqrt == 0) re_build();
    if (t == 1) {
      New.push_back(v);
    }
    if (t == 2) {
      ans = dist[v];
      for (int j = 0; j < (int)New.size(); j++) ans = min(ans, len(v, New[j]));
      printf("%d\n", ans);
    }
  }
  return 0;
}
