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 N = 100010;
const int M = 20;
const int MAGIC = 1000;
const int INF = 0x3f3f3f3f;
struct Edge {
  int v, next;
} e[N * 2];
int head[N], tot;
int n, m;
bool red[N];
int mindist[N];
void init() {
  memset(head, 0xff, sizeof head);
  tot = 0;
}
void addedge(int u, int v) {
  e[tot].v = v;
  e[tot].next = head[u];
  head[u] = tot++;
}
struct LCA {
  int id, dep[2 * N], E[2 * N], R[N];
  int d[M], st[2 * N][M];
  void initRMQ() {
    int i, j;
    dfs(0, -1, 0);
    for (d[0] = 1, i = 1; i < M; i++) d[i] = 2 * d[i - 1];
    for (i = 0; i < id; i++) st[i][0] = i;
    int k = int(log2(1.0 * id)) + 1;
    for (j = 1; j < k; j++) {
      for (i = 0; i < id; i++) {
        if (i + d[j - 1] - 1 < id) {
          st[i][j] = dep[st[i][j - 1]] > dep[st[i + d[j - 1]][j - 1]]
                         ? st[i + d[j - 1]][j - 1]
                         : st[i][j - 1];
        } else {
          break;
        }
      }
    }
  }
  void dfs(int u, int fa, int d) {
    R[u] = id;
    E[id] = u;
    dep[id++] = d;
    for (int j = head[u]; ~j; j = e[j].next) {
      int v = e[j].v;
      if (v == fa) continue;
      dfs(v, u, d + 1);
      E[id] = u;
      dep[id++] = d;
    }
  }
  int getLCA(int u, int v) {
    int x = R[u], y = R[v];
    if (x > y) swap(x, y);
    int k = int(log2(1.0 * (y - x + 1)));
    return E[dep[st[x][k]] > dep[st[y - d[k] + 1][k]] ? st[y - d[k] + 1][k]
                                                      : st[x][k]];
  }
  int query(int u, int v) {
    int x = R[u], y = R[v];
    if (x > y) swap(x, y);
    return dep[x] + dep[y] - 2 * dep[R[getLCA(u, v)]];
  }
} lca;
struct Tree {
  int distDown[N][2], distUp[N];
  void dfs1(int u, int fa) {
    distDown[u][0] = distDown[u][1] = INF;
    if (red[u]) distDown[u][0] = 0;
    for (int j = head[u]; ~j; j = e[j].next) {
      int v = e[j].v;
      if (v == fa) continue;
      dfs1(v, u);
      if (distDown[v][0] + 1 < distDown[u][0]) {
        distDown[u][1] = distDown[u][0];
        distDown[u][0] = distDown[v][0] + 1;
      } else if (distDown[v][0] + 1 < distDown[u][1]) {
        distDown[u][1] = distDown[v][0] + 1;
      }
    }
  }
  void dfs2(int u, int fa) {
    if (fa != -1) {
      distUp[u] = red[fa] ? 1 : INF;
      if (distDown[fa][0] - 1 == distDown[u][0]) {
        distUp[u] = min(distUp[u], distDown[fa][1] + 1);
      } else {
        distUp[u] = min(distUp[u], distDown[fa][0] + 1);
      }
      distUp[u] = min(distUp[u], distUp[fa] + 1);
    }
    for (int j = head[u]; ~j; j = e[j].next) {
      int v = e[j].v;
      if (v == fa) continue;
      dfs2(v, u);
    }
  }
  void work() {
    dfs1(0, -1);
    distUp[0] = INF;
    dfs2(0, -1);
    for (int i = 0; i < n; i++) {
      mindist[i] = min(distUp[i], distDown[i][0]);
    }
  }
} tree;
int main() {
  init();
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--;
    v--;
    addedge(u, v);
    addedge(v, u);
  }
  lca.initRMQ();
  red[0] = 1;
  tree.work();
  vector<int> redId;
  for (int i = 0; i < m; i++) {
    int t, v;
    scanf("%d%d", &t, &v);
    v--;
    if (t == 1) {
      red[v] = 1;
      redId.push_back(v);
    } else {
      int ans = mindist[v];
      for (auto &now : redId) {
        ans = min(ans, lca.query(v, now));
        if (ans == 0) break;
      }
      printf("%d\n", ans);
    }
    if (i % MAGIC == 0) {
      redId.clear();
      tree.work();
    }
  }
  return 0;
}
