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 int MAXN = 1e5 + 5;
const int INF = 1e9;
void fio() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
struct CentroidDecompos {
  vector<set<int>> v;
  vector<int> dad, sz, ds, an;
  vector<vector<int>> par;
  int nn, lgn = 20;
  CentroidDecompos(vector<set<int>> &v) : v(v) {
    nn = v.size();
    ds.resize(nn, 0);
    dad.resize(nn);
    sz.resize(nn);
    an.assign(nn, INF);
    par.assign(nn, vector<int>(21, 0));
    inidfs(0, -1);
    build(0, -1);
  }
  void build(int u, int p) {
    int n = dfs(u, -1);
    int cent = centroid(u, -1, n);
    dad[cent] = p == -1 ? cent : p;
    for (auto i : v[cent]) {
      v[i].erase(cent);
      build(i, cent);
    }
    v[cent].clear();
  }
  int dfs(int u, int p) {
    sz[u] = 1;
    for (auto i : v[u])
      if (i != p) sz[u] += dfs(i, u);
    return sz[u];
  }
  void inidfs(int u, int p) {
    if (p != -1) par[u][0] = p;
    for (int i = 1; i <= lgn; i++) par[u][i] = par[par[u][i - 1]][i - 1];
    for (auto i : v[u])
      if (i != p) {
        ds[i] = ds[u] + 1;
        inidfs(i, u);
      }
  }
  int centroid(int u, int p, int n) {
    for (auto i : v[u])
      if (i != p && sz[i] > (n / 2)) return centroid(i, u, n);
    return u;
  }
  int lca(int u, int v) {
    if (ds[u] > ds[v]) swap(u, v);
    int dd = ds[v] - ds[u];
    for (int i = 0; i <= lgn; i++)
      if (dd >> i & 1) v = par[v][i];
    if (u == v) return u;
    for (int i = lgn; i >= 0; i--)
      if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
  }
  int dis(int u, int x) { return ds[u] + ds[x] - 2 * ds[lca(u, x)]; }
  void up(int u) {
    int x = u;
    while (1) {
      an[x] = min(an[x], dis(u, x));
      if (dad[x] == x) break;
      x = dad[x];
    }
  }
  int qu(int u) {
    int x = u;
    int ans = INF;
    while (1) {
      ans = min(ans, an[x] + dis(u, x));
      if (dad[x] == x) break;
      x = dad[x];
    }
    return ans;
  }
};
int main() {
  fio();
  int n, m;
  cin >> n >> m;
  vector<set<int>> v(n);
  for (int i = 0; i < (n - 1); i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    v[a].insert(b);
    v[b].insert(a);
  }
  CentroidDecompos cd(v);
  cd.up(0);
  while (m--) {
    int t, u;
    cin >> t >> u;
    if (t == 1) {
      cd.up(--u);
    } else {
      cout << cd.qu(--u) << endl;
    }
  }
  return 0;
}
