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;
vector<int> v[100005];
int par[100005][20], h[100005];
void dfs(int node, int p) {
  par[node][0] = p;
  h[node] = h[p] + 1;
  for (int i = 1; i < 20; i++) par[node][i] = par[par[node][i - 1]][i - 1];
  for (int i = 0; i < v[node].size(); i++) {
    if (v[node][i] != p) dfs(v[node][i], node);
  }
}
int query(int x, int y) {
  int ans = 0;
  if (h[x] > h[y]) swap(x, y);
  for (int i = 19; i >= 0; i--) {
    if (h[par[y][i]] >= h[x]) {
      ans += (1 << i);
      y = par[y][i];
    }
  }
  if (x == y) return ans;
  for (int i = 19; i >= 0; i--) {
    if (par[x][i] != par[y][i]) {
      ans += (1 << (i + 1));
      x = par[x][i];
      y = par[y][i];
    }
  }
  ans += 2;
  return ans;
}
int red[100005], clos[100005];
void sim_bfs(int n) {
  queue<int> q;
  for (int i = 1; i <= n; i++) {
    clos[i] = -1;
    if (red[i] == 1) {
      q.push(i);
      clos[i] = 0;
    }
  }
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < v[x].size(); i++) {
      if (clos[v[x][i]] == -1) {
        clos[v[x][i]] = clos[x] + 1;
        q.push(v[x][i]);
      }
    }
  }
}
int main() {
  int i, j, k, n, m;
  scanf("%d", &n);
  scanf("%d", &m);
  for (i = 1; i < n; i++) {
    scanf("%d", &j);
    scanf("%d", &k);
    v[j].push_back(k);
    v[k].push_back(j);
  }
  dfs(1, 0);
  red[1] = 1;
  sim_bfs(n);
  int y = sqrt(m), x;
  while (m != 0) {
    vector<int> vec;
    x = min(y, m);
    m -= x;
    while (x--) {
      scanf("%d", &i);
      if (i == 1) {
        scanf("%d", &j);
        red[j] = 1;
        vec.push_back(j);
      } else {
        scanf("%d", &j);
        int ans = clos[j];
        for (k = 0; k < vec.size(); k++) {
          ans = min(ans, query(j, vec[k]));
        }
        printf("%d\n", ans);
      }
    }
    sim_bfs(n);
  }
  return 0;
}
