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;
int N, M;
int red[100005], path[100005], lca[100005][20], d[100005];
vector<int> v, V[100005];
void dfs(int node, int ata) {
  d[node] = d[ata] + 1;
  lca[node][0] = ata;
  for (typeof(V[node].begin()) it = V[node].begin(); it != V[node].end(); it++)
    if (*it != ata) dfs(*it, node);
}
int LCA(int x, int y) {
  if (d[x] < d[y]) swap(x, y);
  int diff = d[x] - d[y];
  for (int i = 0; i <= 18; i++)
    if (diff & (1 << i)) x = lca[x][i];
  if (x == y) return x;
  for (int i = 18; i >= 0; i--)
    if (lca[x][i] != lca[y][i]) {
      x = lca[x][i];
      y = lca[y][i];
    }
  return lca[x][0];
}
int dist(int x, int y) { return d[x] + d[y] - 2 * d[LCA(x, y)]; }
void again() {
  for (int i = 0; i <= 100004; i++) path[i] = 2000000000;
  queue<pair<int, int> > Q;
  int node, cost;
  v.clear();
  for (int i = 1; i <= N; i++)
    if (red[i]) {
      Q.push(make_pair(i, 0));
      path[i] = 0;
    }
  while (!Q.empty()) {
    node = Q.front().first;
    cost = Q.front().second;
    Q.pop();
    for (typeof(V[node].begin()) it = V[node].begin(); it != V[node].end();
         it++)
      if (path[*it] == 2000000000) {
        path[*it] = cost + 1;
        Q.push(make_pair(*it, path[*it]));
      }
  }
}
int main() {
  ios::sync_with_stdio(0);
  int x, y, cmd;
  cin >> N >> M;
  for (int i = 1; i <= N - 1; i++) {
    cin >> x >> y;
    V[x].push_back(y);
    V[y].push_back(x);
  }
  dfs(1, 0);
  for (int d = 1; d <= 18; d++)
    for (int i = 1; i <= N; i++) lca[i][d] = lca[lca[i][d - 1]][d - 1];
  red[1] = true;
  again();
  v.push_back(1);
  for (int i = 1; i <= M; i++) {
    cin >> cmd >> x;
    if (cmd == 1) {
      red[x] = 1;
      v.push_back(x);
      continue;
    }
    for (typeof(v.begin()) it = v.begin(); it != v.end(); it++)
      path[x] = min(path[x], dist(x, *it));
    cout << path[x] << endl;
    if (i % 316 == 0) again();
  }
  cerr << "\nTime: " << (double)clock() / CLOCKS_PER_SEC << " seconds." << endl;
  return 0;
}
