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> tree[1 << 20];
vector<int> temp;
int tin[1 << 20], tout[1 << 20], pv[1 << 20], subsize[1 << 20], ans[1 << 20];
int timer, par[1 << 20][22], dist[1 << 20];
void dfs(int v, int _depth) {
  dist[v] = _depth;
  subsize[v] = 1;
  tin[v] = ++timer;
  par[v][0] = pv[v];
  for (int i = 1; i <= 19; i++) par[v][i] = par[par[v][i - 1]][i - 1];
  for (int i = 0; i < tree[v].size(); i++) {
    int to = tree[v][i];
    if (to == pv[v]) continue;
    pv[to] = v;
    dfs(to, _depth + 1);
    subsize[v] += subsize[to];
  }
  tout[v] = ++timer;
}
bool upper(int a, int b) { return (tin[a] <= tin[b] && tout[a] >= tout[b]); }
int lca(int a, int b) {
  if (upper(a, b)) return a;
  if (upper(b, a)) return b;
  for (int i = 19; i >= 0; i--)
    if (!upper(par[a][i], b)) a = par[a][i];
  return par[a][0];
}
int distance(int a, int b, int c) { return dist[a] + dist[b] - 2 * dist[c]; }
void bfs() {
  int i, j;
  queue<pair<int, int> > q;
  for (int i = 0; i < temp.size(); i++) {
    q.push(pair<int, int>(temp[i], 0));
    ans[temp[i]] = 0;
  }
  while (!q.empty()) {
    pair<int, int> p = q.front();
    int u = p.first;
    int d = p.second;
    q.pop();
    for (int i = 0; i < tree[u].size(); i++) {
      if (ans[tree[u][i]] > d + 1) {
        ans[tree[u][i]] = d + 1;
        q.push(pair<int, int>(tree[u][i], d + 1));
      }
    }
  }
}
int main() {
  int n, m;
  scanf("%d", &n);
  scanf("%d", &m);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    scanf("%d", &u);
    scanf("%d", &v);
    u--;
    v--;
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  dfs(0, 0);
  pv[0] = 0;
  for (int i = 0; i < n; i++) ans[i] = dist[i];
  while (m--) {
    int type, x;
    scanf("%d", &type);
    scanf("%d", &x);
    x--;
    if (type == 1)
      temp.push_back(x);
    else {
      int minm = ans[x];
      for (int i = 0; i < temp.size(); i++) {
        int l = lca(x, temp[i]);
        minm = min(minm, distance(x, temp[i], l));
      }
      printf("%d\n", minm);
    }
    if (temp.size() > 300) {
      bfs();
      temp.clear();
    }
  }
  return 0;
}
