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> adj[(int)1e5 + 10];
int n, m, total;
int subsize[(int)1e5 + 10], depth[(int)1e5 + 10], ans[(int)1e5 + 10],
    par[(int)1e5 + 10], chosen[(int)1e5 + 10];
int dp[(int)20][(int)1e5 + 10];
void dfs(int u) {
  for (auto it = adj[u].begin(); it != adj[u].end(); it++)
    if (*it != dp[0][u]) {
      dp[0][*it] = u;
      depth[*it] = depth[u] + 1;
      dfs(*it);
    }
}
void preprocess() {
  dp[0][1] = -1;
  depth[1] = 0;
  dfs(1);
  for (int i = 1; i < (int)20; i++)
    for (int j = 1; j <= n; j++) dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
int lca(int u, int v) {
  if (depth[u] > depth[v]) swap(u, v);
  int diff = depth[v] - depth[u];
  for (int i = 0; i < (int)20; i++)
    if (diff & (1 << i)) v = dp[i][v];
  if (v != u) {
    for (int i = (int)20 - 1; i >= 0; i--)
      if (dp[i][u] != dp[i][v]) u = dp[i][u], v = dp[i][v];
    u = dp[0][u];
  }
  return u;
}
int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
void sizecalc(int v, int p) {
  total++;
  subsize[v] = 1;
  for (auto it = adj[v].begin(); it != adj[v].end(); it++)
    if (*it != p && !chosen[*it]) {
      sizecalc(*it, v);
      subsize[v] += subsize[*it];
    }
}
int findCentroid(int v, int p) {
  for (auto it = adj[v].begin(); it != adj[v].end(); it++)
    if (*it != p && !chosen[*it] && subsize[*it] > total / 2)
      return findCentroid(*it, v);
  return v;
}
void decompose(int v, int p) {
  total = 0;
  sizecalc(v, v);
  int centroid = findCentroid(v, v);
  if (p == 0) p = centroid;
  par[centroid] = p;
  chosen[centroid] = true;
  for (auto it = adj[centroid].begin(); it != adj[centroid].end(); it++)
    if (*it != p && !chosen[*it]) decompose(*it, centroid);
}
void update(int v) {
  int x = v;
  while (1) {
    ans[x] = min(ans[x], dist(x, v));
    if (x == par[x]) break;
    x = par[x];
  }
}
int query(int v) {
  int val = (int)1e7, x = v;
  while (1) {
    val = min(val, dist(x, v) + ans[x]);
    if (x == par[x]) break;
    x = par[x];
  }
  return val;
}
int main() {
  int x, y;
  cin >> n >> m;
  for (int i = 1; i < n; i++)
    cin >> x >> y, adj[x].push_back(y), adj[y].push_back(x);
  memset(chosen, false, sizeof(chosen));
  preprocess();
  decompose(1, 0);
  for (int i = 1; i <= n; i++) ans[i] = (int)1e7;
  update(1);
  while (m--) {
    cin >> x >> y;
    if (x == 1)
      update(y);
    else
      cout << query(y) << endl;
  }
  return 0;
}
