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 INF = 0x3f3f3f3f, N = 1e5 + 10, S = 310;
template <class T>
inline bool chkmin(T &A, T B) {
  return B < A ? A = B, 1 : 0;
}
template <class T>
inline bool chkmax(T &A, T B) {
  return A < B ? A = B, 1 : 0;
}
template <const int Maxn, const int Maxm>
struct Link_List {
  int tot, Head[Maxn], Next[Maxm], W[Maxm];
  inline void Add(int first, int second) {
    Next[++tot] = Head[first];
    W[Head[first] = tot] = second;
  }
  inline int operator[](int first) { return W[first]; }
};
Link_List<N, N << 1> E;
int n, m, Mn[N];
int dep[N], Log2[N << 1], id[N], st[N << 1][20], tot;
vector<int> A;
void dfs(int first, int f) {
  dep[first] = dep[f] + 1;
  st[++tot][0] = first;
  id[first] = tot;
  for (int i = (E).Head[first]; i; i = (E).Next[i])
    if (E[i] != f) {
      dfs(E[i], first);
      st[++tot][0] = first;
    }
}
void Build() {
  for (int i = (tot), i_end = (1); i >= i_end; --i)
    for (int j = 1; i + (1 << j) - 1 <= tot; ++j)
      st[i][j] = dep[st[i][j - 1]] < dep[st[i + (1 << (j - 1))][j - 1]]
                     ? st[i][j - 1]
                     : st[i + (1 << (j - 1))][j - 1];
}
int LCA(int first, int second) {
  first = id[first], second = id[second];
  if (first > second) swap(first, second);
  int k = Log2[second - first + 1];
  return dep[st[first][k]] < dep[st[second - (1 << k) + 1][k]]
             ? st[first][k]
             : st[second - (1 << k) + 1][k];
}
int dis(int first, int second) {
  return dep[first] + dep[second] - 2 * dep[LCA(first, second)];
}
void BFS() {
  queue<int> que;
  for (int i = (0), i_end = (A.size() - 1); i <= i_end; ++i)
    if (chkmin(Mn[A[i]], 0)) que.push(A[i]);
  A.clear();
  while (!que.empty()) {
    int first = que.front();
    que.pop();
    for (int i = (E).Head[first]; i; i = (E).Next[i])
      if (chkmin(Mn[E[i]], Mn[first] + 1)) que.push(E[i]);
  }
}
int main() {
  int first, second;
  scanf("%d%d", &n, &m);
  for (int i = (1), i_end = (n - 1); i <= i_end; ++i) {
    scanf("%d%d", &first, &second);
    E.Add(first, second);
    E.Add(second, first);
  }
  A.push_back(1);
  memset(Mn, 63, sizeof(Mn));
  Log2[1] = 0;
  for (int i = (2), i_end = (N * 2 - 10); i <= i_end; ++i)
    Log2[i] = Log2[i - 1] + (1 << (Log2[i - 1] + 1) == i);
  dfs(1, 0);
  Build();
  while (m--) {
    scanf("%d%d", &second, &first);
    if (second == 1) {
      A.push_back(first);
      if (A.size() > S) BFS();
    } else {
      int res = Mn[first];
      for (int i = (0), i_end = (A.size() - 1); i <= i_end; ++i)
        chkmin(res, dis(first, A[i]));
      printf("%d\n", res);
    }
  }
  return 0;
}
