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;
const double PI = 3.141592653589793238463;
const long long mod = 1000000007;
template <typename T, typename U>
std::pair<T, U> operator+(const std::pair<T, U>& l, const std::pair<T, U>& r) {
  return {l.first + r.first, l.second + r.second};
}
const int N = 100001;
const int M = 20;
int dep[N];
int P[N][M];
bool red[N];
int D[N];
vector<int> A[N];
const int LEN = 1000;
int R[LEN];
void go(int z, int x) {
  for (auto y : A[x])
    if (y != z) {
      dep[y] = dep[x] + 1;
      P[y][0] = x;
      for (int i = (1); i <= (M - 1); i++) P[y][i] = P[P[y][i - 1]][i - 1];
      go(x, y);
    }
}
void cal1(int z, int x) {
  if (red[x]) D[x] = 0;
  for (auto y : A[x])
    if (z != y) {
      cal1(x, y);
      D[x] = (D[x] < 1 + D[y]) ? D[x] : 1 + D[y];
    }
}
void cal2(int z, int x) {
  for (auto y : A[x])
    if (z != y) {
      D[y] = (D[y] < 1 + D[x]) ? D[y] : 1 + D[x];
      cal2(x, y);
    }
}
void cal() {
  for (int i = 0; i < (N); i++) D[i] = mod;
  cal1(0, 1);
  cal2(0, 1);
}
int main() {
  red[1] = 1;
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < (n - 1); i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    A[a].push_back(b);
    A[b].push_back(a);
  }
  go(0, 1);
  int len = 0;
  for (int i = 0; i < (m); i++) {
    if (i % LEN == 0) {
      cal();
      len = 0;
    }
    int tp, v;
    scanf("%d %d", &tp, &v);
    if (tp == 1) {
      red[v] = 1;
      R[len++] = v;
    } else {
      int ans = D[v];
      for (int j = 0; j < (len); j++) {
        int r = R[j];
        int vv = v;
        int diff = dep[r] > dep[v] ? dep[r] - dep[v] : dep[v] - dep[r];
        if (dep[r] < dep[v]) {
          for (int k = 0; k < (M); k++)
            if ((1 << (k)) & diff) v = P[v][k];
        } else {
          for (int k = 0; k < (M); k++)
            if ((1 << (k)) & diff) r = P[r][k];
        }
        for (int k = M - 1; k >= 0; --k)
          if (P[v][k] != P[r][k]) {
            v = P[v][k];
            r = P[r][k];
            diff += (1 << (k + 1));
          }
        if (v != r) diff += 2;
        ans = (ans < diff) ? ans : diff;
        v = vv;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}
