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 di[] = {0, 0, 1, -1};
const int dj[] = {1, -1, 0, 0};
const long long MOD = 1e9 + 9;
const long long INF = 1e9;
const long double EPS = 1e-6;
int n;
vector<vector<int> > adj;
vector<bool> vis;
map<pair<int, int>, int> dist;
vector<int> subTreeSize;
int subTreeSizeDFS(int node, int prnt, int start, int startDist = 1) {
  subTreeSize[node] = 1;
  dist[pair<int, int>(node, start)] = dist[pair<int, int>(start, node)] =
      startDist;
  for (auto& i : adj[node]) {
    if (i != prnt && !vis[i])
      subTreeSize[node] += subTreeSizeDFS(i, node, start, startDist + 1);
  }
  return subTreeSize[node];
}
int getCentroid(int node, int curPrnt) {
  int prv = -1;
  subTreeSizeDFS(node, -1, curPrnt);
  int sz = subTreeSize[node];
  for (int i = 0; i < (int)adj[node].size(); i++) {
    if (!vis[adj[node][i]] && adj[node][i] != prv &&
        subTreeSize[adj[node][i]] > sz / 2) {
      prv = node;
      node = adj[node][i];
      i = -1;
    }
  }
  return node;
}
vector<int> prnt;
void decomposeCentroid() {
  vis.assign(n, false);
  prnt.assign(n, 0);
  subTreeSize.assign(n, 0);
  queue<pair<int, int> > q;
  q.emplace(0, -1);
  while (!q.empty()) {
    int cur = q.front().first;
    int prvCent = q.front().second;
    q.pop();
    cur = getCentroid(cur, prvCent);
    prnt[cur] = prvCent;
    vis[cur] = true;
    for (auto& i : adj[cur]) {
      if (!vis[i]) {
        q.emplace(i, cur);
      }
    }
  }
}
vector<int> mnRed;
void queryPaint(int node) {
  int cur = node;
  mnRed[node] = 0;
  while (~prnt[cur]) {
    cur = prnt[cur];
    mnRed[cur] = min(mnRed[cur], dist[pair<int, int>(cur, node)]);
  }
}
int queryClosest(int node) {
  int cur = node;
  int ret = mnRed[node];
  while (~prnt[cur]) {
    cur = prnt[cur];
    ret = min(ret, mnRed[cur] + dist[pair<int, int>(cur, node)]);
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int m;
  cin >> n >> m;
  adj.assign(n, vector<int>());
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  decomposeCentroid();
  mnRed.assign(n, INF);
  queryPaint(0);
  while (m--) {
    int t, v;
    cin >> t >> v;
    v--;
    if (t == 1) {
      queryPaint(v);
    } else {
      cout << queryClosest(v) << endl;
    }
  }
  cin.ignore(), cin.get();
}
