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 long long N = 1e5 + 5;
vector<long long> adj[N];
vector<long long> centroidTree[N];
bool centroidMarked[N];
long long par_ct[N];
long long subsize[N];
long long level[N] = {}, par[N][20];
long long cnt[N];
void DFS(long long x, long long p) {
  par_ct[x] = p;
  for (long long i : centroidTree[x])
    if (i != p) DFS(i, x);
}
void DFS_1(long long x, long long p, long long cnt) {
  level[x] = cnt;
  par[x][0] = p;
  for (auto i : adj[x]) {
    if (i != p) {
      DFS_1(i, x, cnt + 1);
    }
  }
}
long long getLCA(long long n1, long long n2) {
  if (level[n1] > level[n2]) swap(n1, n2);
  long long d = level[n2] - level[n1];
  while (d > 0) {
    long long x = log2(d);
    n2 = par[n2][x];
    d -= (1 << x);
  }
  if (n1 == n2) return n1;
  d = level[n1];
  d = log2(d) + 1;
  for (long long i = d; i >= 0; i--) {
    if (par[n2][i] != -1 && par[n2][i] != par[n1][i]) {
      n2 = par[n2][i];
      n1 = par[n1][i];
    }
  }
  return par[n2][0];
}
long long dist(long long x, long long y) {
  long long z = getLCA(x, y);
  return abs(level[x] - level[z]) + abs(level[y] - level[z]);
}
void get_subtree_sizes(long long src, long long p) {
  subsize[src] = 1;
  for (long long i : adj[src]) {
    if (i != p && !centroidMarked[i]) {
      get_subtree_sizes(i, src);
      subsize[src] += subsize[i];
    }
  }
}
long long get_centroid(long long node, long long p, long long cnt) {
  for (long long i : adj[node]) {
    if (i != p && !centroidMarked[i] && subsize[i] > cnt / 2)
      node = get_centroid(i, node, cnt);
  }
  return node;
}
long long CentroidDecomposition(long long root) {
  get_subtree_sizes(root, -1);
  long long centroid = get_centroid(root, -1, subsize[root]);
  centroidMarked[centroid] = true;
  for (long long it : adj[centroid]) {
    if (!centroidMarked[it]) {
      long long cntd_subtr = CentroidDecomposition(it);
      centroidTree[cntd_subtr].push_back(centroid);
      centroidTree[centroid].push_back(cntd_subtr);
    }
  }
  return centroid;
}
void build(long long node, long long par) {
  while (par != -1) {
    if (cnt[node] < 1e6) cnt[par] = min(cnt[par], cnt[node] + dist(par, node));
    par = par_ct[par];
  }
}
long long query(long long node, long long par) {
  while (par != -1) {
    if (cnt[par] < 1e6) cnt[node] = min(cnt[node], cnt[par] + dist(par, node));
    par = par_ct[par];
  }
  return cnt[node];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n, k, x, y;
  cin >> n >> k;
  for (long long i = 1; i < n; i++) {
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  long long root = CentroidDecomposition(1);
  DFS(root, -1);
  DFS_1(1, -1, 0);
  for (long long j = 1; j < 20; j++) {
    for (long long i = 1; i <= n; i++) {
      int x = par[i][j - 1];
      if (x != -1) par[i][j] = par[x][j - 1];
    }
  }
  memset(cnt, 1e6, sizeof(cnt));
  cnt[1] = 0;
  build(1, par_ct[1]);
  while (k--) {
    cin >> x >> y;
    if (x == 1) {
      cnt[y] = 0;
      build(y, par_ct[y]);
    } else {
      cout << query(y, par_ct[y]) << "\n";
    }
  }
  return 0;
}
