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;
vector<int> adjList[100010];
bool valid[100010];
int CP[100010];
int CL[100010];
map<int, int> CD[100010];
int CA[100010];
int cnt[100010];
int dfs(int u, int p) {
  cnt[u] = 1;
  for (auto v : adjList[u])
    if (v != p && valid[v]) cnt[u] += dfs(v, u);
  return cnt[u];
}
int dfs2(int u, int p, int limit) {
  for (auto v : adjList[u])
    if (v != p && valid[v] && 2 * cnt[v] > limit) return dfs2(v, u, limit);
  return u;
}
void dfs3(int u, int p, int d, int c) {
  CD[c][u] = d;
  for (auto v : adjList[u])
    if (v != p && valid[v]) dfs3(v, u, d + 1, c);
}
int find_centroid(int u) {
  int total = dfs(u, -1);
  int cent = dfs2(u, -1, total);
  dfs3(cent, -1, 0, cent);
  return cent;
}
void reddify(int u) {
  for (int x = u; x != -1; x = CP[x]) CA[x] = min(CA[x], CD[x][u]);
}
int getRed(int u) {
  int mind = 1 << 20;
  for (int x = u; x != -1; x = CP[x]) mind = min(mind, CD[x][u] + CA[x]);
  return mind;
}
int main() {
  int N, M;
  cin >> N >> M;
  for (int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    adjList[x].push_back(y);
    adjList[y].push_back(x);
  }
  for (int i = 0; i < N; i++) valid[i] = true;
  queue<pair<int, int> > q;
  q.push(make_pair(0, -1));
  while (!q.empty()) {
    int u = q.front().first;
    int p = q.front().second;
    q.pop();
    u = find_centroid(u);
    CP[u] = p;
    CL[u] = (p != -1 ? CL[p] + 1 : -1);
    for (auto v : adjList[u])
      if (valid[v]) q.push(make_pair(v, u));
    valid[u] = false;
  }
  for (int i = 0; i < N; i++) CA[i] = 1 << 20;
  reddify(0);
  for (int n = 0; n < M; n++) {
    int t, u;
    cin >> t >> u;
    u--;
    if (t == 1)
      reddify(u);
    else
      cout << getRed(u) << endl;
  }
  return 0;
}
