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 depth[100005], sz[100005], p[100005][20], ans[100005], n, m;
set<int> g[100005];
int parcentroid[100005];
void dfs1(int node, int par) {
  depth[node] = depth[par] + 1;
  p[node][0] = par;
  for (int i = 1; i < 20; i++) p[node][i] = p[p[node][i - 1]][i - 1];
  for (auto it : g[node]) {
    if (it != par) dfs1(it, node);
  }
}
void dfs(int node, int par) {
  sz[node] = 1;
  for (auto it : g[node]) {
    if (it != par) {
      dfs(it, node);
      sz[node] += sz[it];
    }
  }
}
int find_centroid(int node, int par, int cnt) {
  for (auto it : g[node]) {
    if (it == par) continue;
    if (sz[it] > cnt / 2) return find_centroid(it, node, cnt);
  }
  return node;
}
void decompose(int node, int par) {
  dfs(node, node);
  int centroid = find_centroid(node, node, sz[node]);
  parcentroid[centroid] = par;
  for (auto it : g[centroid]) {
    g[it].erase(centroid);
    decompose(it, centroid);
  }
  g[centroid].clear();
}
int lca(int x, int y) {
  if (depth[x] > depth[y]) swap(x, y);
  for (int i = 20 - 1; i >= 0; i--) {
    if ((depth[y] - (1 << i)) >= depth[x]) y = p[y][i];
  }
  if (x == y) return x;
  for (int i = 20 - 1; i >= 0; i--) {
    if (p[x][i] != p[y][i]) {
      x = p[x][i];
      y = p[y][i];
    }
  }
  return p[x][0];
}
int dist(int x, int y) {
  return (depth[x] + depth[y] - (2 * depth[lca(x, y)]));
}
void update(int node) {
  int cur = node;
  while (cur) {
    ans[cur] = min(ans[cur], dist(node, cur));
    cur = parcentroid[cur];
  }
}
int query(int node) {
  int cur = node, res = 10000000;
  while (cur) {
    res = min(res, ans[cur] + dist(node, cur));
    cur = parcentroid[cur];
  }
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[x].insert(y);
    g[y].insert(x);
  }
  dfs1(1, 0);
  decompose(1, 0);
  for (int i = 1; i <= n; i++) ans[i] = 10000000;
  update(1);
  while (m--) {
    int t, x;
    scanf("%d%d", &t, &x);
    if (t == 1)
      update(x);
    else {
      int res = query(x);
      printf("%d\n", res);
    }
  }
  return 0;
}
