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;
set<int> g[100001], og[100001];
int par[100001], sub[100001], dp[100001], pb[100001], visited[100001],
    lev[100001];
vector<int> bl[100001];
void dfs(int node) {
  visited[node] = 1;
  for (auto i : og[node]) {
    if (!visited[i]) {
      pb[i] = node;
      lev[i] = lev[node] + 1;
      dfs(i);
    }
  }
}
int subCal(int node, int p) {
  sub[node] = 1;
  for (auto i : g[node]) {
    if (i != p) sub[node] += subCal(i, node);
  }
  return sub[node];
}
int centroidCal(int node, int p, int n) {
  for (auto i : g[node]) {
    if (i != p && sub[i] > n / 2) return centroidCal(i, node, n);
  }
  return node;
}
void decompose(int node, int p) {
  int size = subCal(node, p);
  int centroid = centroidCal(node, p, size);
  par[centroid] = p;
  for (auto i : g[centroid]) {
    g[i].erase(centroid);
    decompose(i, centroid);
  }
}
int dis(int a, int b) {
  int sum = 0;
  for (int i = 17; i >= 0; i--) {
    if (lev[a] <= lev[b]) break;
    if (bl[a][i] != -1 && ((1 << i) <= (lev[a] - lev[b]))) {
      a = bl[a][i];
      sum += (1 << i);
    }
  }
  for (int i = 17; i >= 0; i--) {
    if (lev[b] <= lev[a]) break;
    if (bl[b][i] != -1 && ((1 << i) <= (lev[b] - lev[a]))) {
      b = bl[b][i];
      sum += (1 << i);
    }
  }
  if (a == b) return sum;
  for (int i = 17; i >= 0; i--) {
    if (bl[a][i] != -1 && bl[b][i] != -1 && bl[a][i] != bl[b][i]) {
      a = bl[a][i];
      b = bl[b][i];
      sum += (1 << (i + 1));
    }
  }
  return (sum + 2);
}
int main() {
  int n, Q;
  cin >> n >> Q;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    g[u].insert(v);
    g[v].insert(u);
    og[u].insert(v);
    og[v].insert(u);
  }
  for (int i = 1; i <= n; i++) {
    dp[i] = 100000000;
    par[i] = -1;
    pb[i] = -1;
    visited[i] = 0;
    lev[i] = 0;
  }
  decompose(1, -1);
  dfs(1);
  dp[1] = 0;
  for (int i = 0; i <= 17; i++) {
    bl[1].push_back(-1);
  }
  for (int j = 2; j <= n; j++) {
    bl[j].assign(18, -1);
    bl[j][0] = pb[j];
  }
  for (int i = 1; i <= 17; i++) {
    for (int j = 2; j <= n; j++) {
      if (bl[j][i - 1] == -1) {
        bl[j][i] = -1;
        continue;
      }
      bl[j][i] = bl[bl[j][i - 1]][i - 1];
    }
  }
  int node = 1;
  int p = par[node];
  while (p != -1) {
    int val = dis(1, p);
    dp[p] = min(dp[p], val);
    node = p;
    p = par[p];
  }
  while (Q--) {
    int t, v;
    cin >> t >> v;
    if (t == 1) {
      int node = v;
      int p = par[node];
      dp[v] = 0;
      while (p != -1) {
        int val = dis(v, p);
        dp[p] = min(dp[p], val);
        node = p;
        p = par[p];
      }
    } else {
      int node = v;
      int ans = dp[node];
      int p = par[node];
      while (p != -1) {
        int val = dis(v, p);
        ans = min(ans, dp[p] + val);
        node = p;
        p = par[p];
      }
      cout << ans << endl;
    }
  }
}
