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;
using ll = long long;
using ld = long double;
set<int> gr[(ll)(1e5 + 3)];
int p[(ll)(1e5 + 3)][20], h[(ll)(1e5 + 3)], cp[(ll)(1e5 + 3)],
    st[(ll)(1e5 + 3)], md[(ll)(1e5 + 3)];
void dfs(int node, int par) {
  h[node] = h[par] + 1;
  p[node][0] = par;
  for (int x : gr[node]) {
    if (x != par) {
      dfs(x, node);
    }
  }
}
void build() {
  for (int j = 1; j < 20; j++) {
    for (int i = 1; i < (ll)(1e5 + 3); i++) {
      if (p[i][j - 1]) {
        p[i][j] = p[p[i][j - 1]][j - 1];
      }
    }
  }
}
void subtree(int node, int par) {
  st[node] = 1;
  for (int x : gr[node]) {
    if (x != par) {
      subtree(x, node);
      st[node] += st[x];
    }
  }
}
int dd(int node, int n, int par) {
  for (int x : gr[node]) {
    if (x != par && st[x] > n / 2) {
      return dd(x, n, node);
    }
  }
  return node;
}
int centroid(int node, int n) {
  node = dd(node, n, 0);
  for (int x : gr[node]) {
    gr[x].erase(node);
    subtree(x, node);
    int cc = centroid(x, st[x]);
    cp[cc] = node;
  }
  gr[node].clear();
  return node;
}
int lca(int u, int v) {
  if (h[v] > h[u]) {
    swap(u, v);
  }
  int d = h[u] - h[v];
  for (int i = 0; i <= 17; i++) {
    if ((d >> i) & 1) {
      u = p[u][i];
    }
  }
  if (u == v) return u;
  for (int i = 17; i >= 0; i--) {
    if (p[u][i] != p[v][i]) {
      u = p[u][i], v = p[v][i];
    }
  }
  return p[u][0];
}
int dis(int u, int v) { return h[u] + h[v] - 2 * h[lca(u, v)]; }
void upd(int node) {
  md[node] = 0;
  int nd = node;
  while (cp[nd]) {
    md[cp[nd]] = min(md[cp[nd]], dis(node, cp[nd]));
    nd = cp[nd];
  }
}
int qur(int node) {
  int nd = node, ma = md[node];
  while (cp[nd]) {
    ma = min(md[cp[nd]] + dis(cp[nd], node), ma);
    nd = cp[nd];
  }
  return ma;
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    gr[u].insert(v);
    gr[v].insert(u);
  }
  for (int i = 1; i <= n; i++) {
    md[i] = (ll)(1e9 + 7);
  }
  dfs(1, 0);
  build();
  subtree(1, n);
  centroid(1, n);
  upd(1);
  for (int i = 0; i < m; i++) {
    int ch, nd;
    scanf("%d %d", &ch, &nd);
    if (ch == 1) {
      upd(nd);
    } else {
      printf("%d\n", qur(nd));
    }
  }
}
