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 = 2e5 + 20;
int col[maxn];
struct node {
  int u, v;
  int tonext;
} e[maxn];
int first[maxn];
int num;
void add(int u, int v) {
  ++num;
  e[num].u = u;
  e[num].v = v;
  e[num].tonext = first[u];
  first[u] = num;
}
int tot[maxn];
int lentot;
int dp[maxn];
struct bfsnode {
  int cur, cnt;
  bfsnode(int a, int b) : cur(a), cnt(b) {}
};
queue<struct bfsnode> que;
bool vis[maxn];
void bfs() {
  memset(vis, false, sizeof vis);
  for (int i = 1; i <= lentot; ++i) {
    que.push(bfsnode(tot[i], 0));
    dp[tot[i]] = 0;
  }
  while (!que.empty()) {
    struct bfsnode t = que.front();
    que.pop();
    for (int i = first[t.cur]; i; i = e[i].tonext) {
      int v = e[i].v;
      if (vis[v]) continue;
      if (dp[v] <= t.cnt + 1) continue;
      vis[v] = true;
      dp[v] = t.cnt + 1;
      que.push(bfsnode(v, t.cnt + 1));
    }
  }
}
int ansc[maxn][25];
int deep[maxn];
int fa[maxn];
void init_LCA(int cur) {
  ansc[cur][0] = fa[cur];
  for (int i = 1; i <= 24; ++i) {
    ansc[cur][i] = ansc[ansc[cur][i - 1]][i - 1];
  }
  for (int i = first[cur]; i; i = e[i].tonext) {
    int v = e[i].v;
    if (v == fa[cur]) continue;
    fa[v] = cur;
    deep[v] = deep[cur] + 1;
    init_LCA(v);
  }
}
int LCA(int x, int y) {
  if (deep[x] < deep[y]) swap(x, y);
  for (int i = 24; i >= 0; --i) {
    if (deep[ansc[x][i]] >= deep[y]) {
      x = ansc[x][i];
    }
  }
  if (x == y) return x;
  for (int i = 24; i >= 0; --i) {
    if (ansc[x][i] != ansc[y][i]) {
      x = ansc[x][i];
      y = ansc[y][i];
    }
  }
  return ansc[x][0];
}
int dis[maxn];
void dfs(int cur, int step) {
  dis[cur] = min(dis[cur], step);
  for (int i = first[cur]; i; i = e[i].tonext) {
    int v = e[i].v;
    if (vis[v]) continue;
    vis[v] = true;
    dfs(v, step + 1);
  }
}
void work() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n - 1; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  memset(dis, 0x3f, sizeof dis);
  dis[1] = 0;
  vis[1] = true;
  dfs(1, 0);
  memset(dp, 0x3f, sizeof dp);
  col[1] = 1;
  tot[++lentot] = 1;
  bfs();
  lentot = 0;
  fa[1] = 1;
  deep[1] = 0;
  init_LCA(1);
  int magic = (int)sqrt(m);
  for (int i = 1; i <= m; ++i) {
    int flag, which;
    scanf("%d%d", &flag, &which);
    if (flag == 1) {
      tot[++lentot] = which;
    } else {
      int ans = dp[which];
      for (int i = 1; i <= lentot; ++i) {
        int haha = LCA(which, tot[i]);
        ans = min(ans, dis[which] + dis[tot[i]] - 2 * dis[haha]);
      }
      printf("%d\n", ans);
    }
    if (lentot >= magic) {
      bfs();
      lentot = 0;
    }
  }
}
int main() {
  work();
  return 0;
}
