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<vector<int> > adj;
int child[1000000], cen[1000000], parent[1000000], lca[100005][20], h[1000000],
    anc, ans[1000000], n, m, u, v, t;
void DFS(int pos, int par) {
  child[pos] = 1;
  for (int i = 0; i < adj[pos].size(); i++) {
    int k = adj[pos][i];
    if (k != par && cen[k] == 0) {
      DFS(k, pos);
      child[pos] += child[k];
    }
  }
}
int solve(int pos, int par, int sz) {
  for (int i = 0; i < adj[pos].size(); i++) {
    int k = adj[pos][i];
    if (k != par && cen[k] == 0 && child[k] * 2 > sz) {
      return solve(k, pos, sz);
    }
  }
  return pos;
}
int centroid(int pos) {
  DFS(pos, 0);
  int res = solve(pos, 0, child[pos]);
  cen[res] = 1;
  for (int i = 0; i < adj[res].size(); i++) {
    int k = adj[res][i];
    if (cen[k] == 0) {
      parent[centroid(k)] = res;
    }
  }
  return res;
}
void LCA(int pos, int par) {
  lca[pos][0] = par;
  h[pos] = h[par] + 1;
  for (int i = 0; i < adj[pos].size(); i++) {
    int k = adj[pos][i];
    if (k != par) LCA(k, pos);
  }
}
int get_lca(int x, int y) {
  if (h[x] < h[y]) {
    x = x + y;
    y = x - y;
    x = x - y;
  }
  int dis = h[x] - h[y];
  for (int i = 0; i <= 18; i++) {
    if (((dis >> i) & 1) == 1) x = lca[x][i];
  }
  for (int i = 18; i >= 0; i--) {
    if (lca[x][i] != lca[y][i] && lca[x][i] != 0) {
      x = lca[x][i];
      y = lca[y][i];
    }
  }
  if (x != y)
    return lca[x][0];
  else
    return x;
}
void update(int pos, int par) {
  while (parent[par] != 0) {
    par = parent[par];
    anc = get_lca(pos, par);
    ans[par] = min(ans[par], h[pos] + h[par] - 2 * h[anc]);
  }
}
int get(int pos, int par) {
  int res = ans[pos];
  while (parent[par] != 0) {
    par = parent[par];
    anc = get_lca(pos, par);
    res = min(res, h[pos] + h[par] - 2 * h[anc] + ans[par]);
  }
  return res;
}
int main() {
  scanf("%d %d", &n, &m);
  adj.resize(n + 1);
  for (int i = 1; i < n; i++) {
    scanf("%d %d", &u, &v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  centroid(1);
  LCA(1, 0);
  for (int i = 1; i <= n; i++) {
    ans[i] = 1000000000;
  }
  for (int j = 1; j <= 18; j++) {
    for (int i = 1; i <= n; i++) {
      lca[i][j] = lca[lca[i][j - 1]][j - 1];
    }
  }
  ans[1] = 0;
  update(1, 1);
  while (m--) {
    scanf("%d %d", &t, &v);
    if (t == 1) {
      ans[v] = 0;
      update(v, v);
    } else {
      printf("%d\n", get(v, v));
    }
  }
}
