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;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int MN = 1e5 + 5, LN = 17, MOD = 1e9 + 7, INF = 0x3f3f3f3f, BSZ = 320;
int N, Q;
vector<int> g[MN];
int sz[MN], par[MN], dep[MN], dis[LN][MN], dp[MN];
bool done[MN];
int getsz(int u, int p) {
  sz[u] = 1;
  for (int v : g[u])
    if (v != p && !done[v]) sz[u] += getsz(v, u);
  return sz[u];
}
int centroid(int u, int p, int s) {
  for (int v : g[u])
    if (v != p && !done[v] && sz[v] > s / 2) return centroid(v, u, s);
  return u;
}
void dfs(int u, int p, int d, int lvl) {
  dis[lvl][u] = d;
  for (int v : g[u])
    if (v != p && !done[v]) dfs(v, u, d + 1, lvl);
}
void go(int u, int p, int lvl) {
  int s = getsz(u, -1);
  int c = centroid(u, -1, s);
  dep[c] = lvl;
  par[c] = p;
  dfs(c, -1, 0, lvl);
  done[c] = true;
  for (int v : g[c])
    if (!done[v]) go(v, c, lvl + 1);
}
void upd(int u) {
  int cur = u;
  while (cur != -1) {
    dp[cur] = min(dp[cur], dis[dep[cur]][u]);
    cur = par[cur];
  }
}
int qry(int u) {
  int ret = INF;
  int cur = u;
  while (cur != -1) {
    ret = min(ret, dp[cur] + dis[dep[cur]][u]);
    cur = par[cur];
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> N >> Q;
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  memset(dp, 0x3f, sizeof(dp));
  go(1, -1, 0);
  upd(1);
  for (int i = 0; i < Q; i++) {
    int t, u;
    cin >> t >> u;
    if (t == 1)
      upd(u);
    else
      cout << qry(u) << '\n';
  }
  return 0;
}
