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;
list<int> Adj[100001];
int vis[100001], parincent[100001];
int Cvis[100001];
int sub_tree[100005], level[100001], pred[100001];
int visited[100005];
int ans[100005];
const int INF = 1000000000;
int check[100001];
int color = 1;
int dp[100005][20];
void dfs(int s) {
  visited[s] = 1;
  list<int>::iterator it;
  for (it = Adj[s].begin(); it != Adj[s].end(); it++) {
    if (!visited[*it]) {
      level[*it] = level[s] + 1;
      pred[*it] = s;
      dfs(*it);
    }
  }
}
void preprocess(int n) {
  for (int i = 0; i < 100004; i++) {
    memset(dp[i], 0, sizeof(dp[i]));
  }
  for (int i = 1; i <= n; i++) {
    dp[i][0] = pred[i];
  }
  for (int j = 1; (1 << j) < n; j++) {
    for (int i = 1; i <= n; i++) {
      if (dp[i][j - 1]) dp[i][j] = dp[dp[i][j - 1]][j - 1];
    }
  }
}
int LCA(int a, int b) {
  if (level[a] < level[b]) swap(a, b);
  while (level[a] > level[b]) {
    int x = log2(level[a] - level[b]);
    a = dp[a][x];
  }
  if (a == b) return a;
  for (int x = log2(level[a]); x >= 0; x--) {
    if (dp[a][x] && dp[a][x] != dp[b][x]) {
      a = dp[a][x];
      b = dp[b][x];
    }
  }
  return pred[a];
}
void sub(int x) {
  vis[x] = color;
  sub_tree[x] = 1;
  for (list<int>::iterator it = Adj[x].begin(); it != Adj[x].end(); ++it) {
    if (vis[*it] != color && !Cvis[*it]) {
      sub(*it);
      sub_tree[x] += sub_tree[*it];
    }
  }
}
int Centroid(int x, int n) {
  ++color;
  sub(x);
  int pi = -1;
  for (; 1;) {
    int max_ele = -1, ele = x;
    for (list<int>::iterator it = Adj[x].begin(); it != Adj[x].end(); ++it)
      if (!Cvis[*it] && max_ele < sub_tree[*it] && *it != pi) {
        max_ele = sub_tree[*it];
        ele = *it;
      }
    if (max_ele <= n / 2)
      return x;
    else {
      pi = x;
      x = ele;
    }
  }
}
int CreateCentroid(int u, int n) {
  int c = Centroid(u, n);
  Cvis[c] = 1;
  for (list<int>::iterator it = Adj[c].begin(); it != Adj[c].end(); ++it) {
    if (!Cvis[*it]) {
      int x = CreateCentroid(*it, n / 2);
      parincent[x] = c;
    }
  }
  return c;
}
void update(int s) {
  int node = s;
  while (1) {
    ans[node] =
        min(ans[node], level[node] + level[s] - 2 * level[LCA(node, s)]);
    if (node == parincent[node]) break;
    node = parincent[node];
  }
}
int query(int s) {
  int node = s;
  int mini = 1000000000;
  while (1) {
    mini =
        min(mini, ans[node] + level[node] + level[s] - 2 * level[LCA(node, s)]);
    if (node == parincent[node]) break;
    node = parincent[node];
  }
  return mini;
}
int main() {
  int N, i, L, R, Q;
  scanf("%d%d", &N, &Q);
  for (i = 0; i < N - 1; ++i) {
    scanf("%d%d", &L, &R);
    Adj[L].push_back(R);
    Adj[R].push_back(L);
  }
  for (i = 0; i <= N; ++i) ans[i] = INF;
  dfs(1);
  preprocess(N);
  int x = CreateCentroid(1, N);
  parincent[x] = x;
  for (i = 1; i <= N; ++i) ans[i] = INF;
  update(1);
  int u, t;
  for (; Q; --Q) {
    scanf("%d%d", &t, &u);
    if (t == 1)
      update(u);
    else
      printf("%d\n", query(u));
  }
  return 0;
}
