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;
int n, q, sq, nr;
vector<int> m[100010];
int dist1[100010];
int dist[100010];
bitset<100010> viz;
vector<int> c;
queue<int> c2;
int nivel[200010];
int noduri[200010];
int poz[200010];
int put[25];
int lg[200010];
int rmq[200010][23];
pair<int, int> quers[100010];
void liniarize(int nod, int level) {
  viz[nod] = 1;
  noduri[++nr] = nod;
  nivel[nr] = level;
  if (poz[nod] == 0) poz[nod] = nr;
  for (vector<int>::iterator it = m[nod].begin(); it != m[nod].end(); it++)
    if (!viz[*it]) {
      liniarize(*it, level + 1);
      noduri[++nr] = nod;
      nivel[nr] = level;
    }
}
int min1(int a, int b) {
  if (nivel[a] <= nivel[b])
    return a;
  else
    return b;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> q;
  sq = sqrt(q);
  int i, j, a, b;
  for (i = 1; i < n; i++) {
    cin >> a >> b;
    m[a].push_back(b);
    m[b].push_back(a);
  }
  for (i = 1; i <= q; i++) {
    cin >> a >> b;
    quers[i] = make_pair(a, b);
  }
  liniarize(1, 0);
  put[0] = 1;
  for (i = 1; i <= 20; i++) put[i] = 2 * put[i - 1];
  for (i = 2; i <= nr; i++) lg[i] = lg[i / 2] + 1;
  for (i = 1; i <= nr; i++) rmq[i][0] = i;
  for (j = 1; put[j] <= nr; j++)
    for (i = 1; i + put[j] - 1 <= nr; i++)
      rmq[i][j] = min1(rmq[i][j - 1], rmq[i + put[j - 1]][j - 1]);
  int len, crt, rosu, l, sol, aux;
  c2.push(1);
  viz.reset();
  while (!c2.empty()) {
    crt = c2.front();
    c2.pop();
    viz[crt] = 1;
    for (i = 0; i < m[crt].size(); i++)
      if (!viz[m[crt][i]]) {
        dist1[m[crt][i]] = dist1[crt] + 1;
        c2.push(m[crt][i]);
      }
  }
  c.push_back(1);
  dist[1] = -1;
  j = 1;
  while (1) {
    len = c.size();
    while (!c2.empty()) c2.pop();
    viz.reset();
    for (i = 0; i < len; i++) {
      crt = c[i];
      viz[crt] = 1;
      for (l = 0; l < m[crt].size(); l++)
        if (!viz[m[crt][l]] && dist[m[crt][l]] != -1) {
          dist[m[crt][l]] = 1;
          viz[m[crt][l]] = 1;
          c2.push(m[crt][l]);
        }
    }
    while (!c2.empty()) {
      crt = c2.front();
      c2.pop();
      for (l = 0; l < m[crt].size(); l++)
        if (!viz[m[crt][l]]) {
          if (dist[m[crt][l]] != 0)
            dist[m[crt][l]] = min(dist[m[crt][l]], dist[crt] + 1);
          else
            dist[m[crt][l]] = dist[crt] + 1;
          viz[m[crt][l]] = 1;
          c2.push(m[crt][l]);
        }
    }
    rosu = 0;
    for (i = j; i < j + sq; i++) {
      if (i > q) return 0;
      if (quers[i].first == 1) {
        c.push_back(quers[i].second);
        dist[quers[i].second] = -1;
        rosu++;
      } else {
        a = quers[i].second;
        sol = dist[a];
        for (l = len; l < c.size(); l++) {
          int a1 = poz[a], b1 = poz[c[l]];
          if (a1 > b1) {
            aux = a1;
            a1 = b1;
            b1 = aux;
          }
          int l1 = lg[b1 - a1 + 1];
          sol = min(sol, dist1[a] + dist1[c[l]] -
                             2 * dist1[noduri[min1(
                                     rmq[a1][l1], rmq[b1 - put[l1] + 1][l1])]]);
        }
        if (sol == -1)
          cout << "0\n";
        else
          cout << sol << '\n';
      }
    }
    j += sq;
  }
  return 0;
}
