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> g[100005];
int n, m, nn;
int c[100005], h[100005], par[100005], d[100005], dont[100005];
int dp[20][100005];
const int INF = 1e9 + 5;
void dfs0(int v) {
  for (vector<int>::iterator it = g[v].begin(); it != g[v].end(); ++it)
    if (*it != dp[0][v]) {
      dp[0][*it] = v;
      h[*it] = h[v] + 1;
      dfs0(*it);
    }
}
void dfs1(int v, int p) {
  c[v] = 1;
  ++nn;
  for (vector<int>::iterator it = g[v].begin(); it != g[v].end(); ++it)
    if (*it != p && !dont[*it]) {
      dfs1(*it, v);
      c[v] += c[*it];
    }
}
int dfs2(int v, int p) {
  for (vector<int>::iterator it = g[v].begin(); it != g[v].end(); ++it)
    if (*it != p && !dont[*it] && c[*it] > nn / 2) return dfs2(*it, v);
  return v;
}
void decompose(int root, int p) {
  nn = 0;
  dfs1(root, root);
  int centroid = dfs2(root, root);
  par[centroid] = p;
  dont[centroid] = 1;
  for (vector<int>::iterator it = g[centroid].begin(); it != g[centroid].end();
       ++it)
    if (!dont[*it]) decompose(*it, centroid);
}
int lca(int u, int v) {
  if (h[u] > h[v]) swap(u, v);
  int dh = h[v] - h[u], i;
  for (i = 0; i < 20; ++i)
    if ((dh >> i) & 1) v = dp[i][v];
  if (u == v) return v;
  for (i = 19; i >= 0; --i)
    if (dp[i][u] != dp[i][v]) u = dp[i][u], v = dp[i][v];
  return dp[0][u];
}
int dist(int u, int v) { return h[u] + h[v] - 2 * h[lca(u, v)]; }
void precompute() {
  dp[0][1] = 1;
  dfs0(1);
  decompose(1, -1);
  int i, j;
  for (i = 1; i < 20; ++i)
    for (j = 1; j <= n; ++j) dp[i][j] = dp[i - 1][dp[i - 1][j]];
  for (i = 1; i <= n; ++i) d[i] = INF;
}
void update(int v) {
  for (int u = v; u != -1; u = par[u]) d[u] = min(d[u], dist(u, v));
}
int query(int v) {
  int u, ans = INF;
  for (u = v; u != -1; u = par[u]) ans = min(ans, dist(u, v) + d[u]);
  return ans;
}
int main() {
  int i, u, v;
  scanf("%d%d", &n, &m);
  for (i = 1; i < n; ++i) {
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  precompute();
  update(1);
  while (m--) {
    scanf("%d%d", &u, &v);
    if (u - 2)
      update(v);
    else
      printf("%d\n", query(v));
  }
  return 0;
}
