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 = 1e5 + 5;
const int LOGN = 20;
const int INF = 1e9 + 7;
int n, m, a, b, currSize, parent[N], subTree[N], level[N], ans[N], dp[LOGN][N];
set<int> graph[N];
void dfs0(int u) {
  for (auto it : graph[u]) {
    if (it != dp[0][u]) {
      dp[0][it] = u;
      level[it] = level[u] + 1;
      dfs0(it);
    }
  }
}
void preprocess() {
  level[0] = 0;
  dp[0][0] = 0;
  dfs0(0);
  for (int i = 1; i < LOGN; i++)
    for (int j = 0; j < n; j++) dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
int lca(int a, int b) {
  if (level[a] > level[b]) swap(a, b);
  int d = level[b] - level[a];
  for (int i = 0; i < LOGN; i++)
    if (d & (1 << i)) b = dp[i][b];
  if (a == b) return a;
  for (int i = LOGN - 1; i >= 0; i--)
    if (dp[i][a] != dp[i][b]) {
      a = dp[i][a];
      b = dp[i][b];
    }
  return dp[0][a];
}
int dist(int a, int b) { return level[a] + level[b] - 2 * level[lca(a, b)]; }
void dfs1(int u, int p) {
  subTree[u] = 1;
  currSize++;
  for (auto it : graph[u]) {
    if (it != p) {
      dfs1(it, u);
      subTree[u] += subTree[it];
    }
  }
}
int dfs2(int u, int p) {
  for (auto it : graph[u]) {
    if (it != p && subTree[it] > currSize / 2) {
      return dfs2(it, u);
    }
  }
  return u;
}
void decompose(int u, int p) {
  currSize = 0;
  dfs1(u, u);
  int centroid = dfs2(u, u);
  if (p == -1) p = centroid;
  parent[centroid] = p;
  for (auto it : graph[centroid]) {
    graph[it].erase(centroid);
    decompose(it, centroid);
  }
  graph[centroid].clear();
}
void update(int u) {
  int x = u;
  while (true) {
    ans[x] = min(ans[x], dist(x, u));
    if (x == parent[x]) break;
    x = parent[x];
  }
}
int query(int u) {
  int x = u;
  int res = INF;
  while (true) {
    res = min(res, dist(x, u) + ans[x]);
    if (x == parent[x]) break;
    x = parent[x];
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n - 1; i++) {
    cin >> a >> b;
    --b;
    --a;
    graph[a].insert(b);
    graph[b].insert(a);
  }
  preprocess();
  decompose(0, -1);
  for (int i = 0; i < n; i++) ans[i] = INF;
  update(0);
  while (m--) {
    cin >> a >> b;
    --b;
    if (a == 1)
      update(b);
    else
      cout << query(b) << "\n";
  }
  return 0;
}
