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 maxn = 1e5 + 7;
const long long mod = 1e9 + 7;
const long long INF = 1e9 + 7;
const long long mlog = 20;
const long long SQ = 400;
long long n;
vector<long long> adj[maxn];
long long sz[maxn];
long long dead[maxn];
long long pr[maxn];
long long par[mlog][maxn];
long long dp[maxn];
long long h[maxn];
void pre_dfs(long long v, long long par = -1) {
  sz[v] = 1;
  for (long long u : adj[v])
    if (u != par && !dead[u]) pre_dfs(u, v), sz[v] += sz[u];
}
long long getCentroid(long long v, long long s, long long par = -1) {
  for (long long u : adj[v])
    if (u != par && !dead[u] && sz[u] > s / 2) return getCentroid(u, s, v);
  return v;
}
void CentroidDecomposition(long long v, long long p = 0) {
  pre_dfs(v);
  long long cen = getCentroid(v, sz[v]);
  dead[cen] = true;
  pr[cen] = p;
  for (long long u : adj[cen])
    if (!dead[u]) CentroidDecomposition(u, cen);
}
long long getpar(long long v, long long l) {
  for (long long j = 0; j < mlog; j++)
    if (l & (1 << j)) v = par[j][v];
  return v;
}
long long lca(long long u, long long v) {
  if (h[u] < h[v]) swap(u, v);
  u = getpar(u, h[u] - h[v]);
  if (u == v) return v;
  for (long long j = mlog - 1; j >= 0; j--) {
    long long p1 = par[j][u];
    long long p2 = par[j][v];
    if (p1 != p2) u = p1, v = p2;
  }
  return par[0][v];
}
long long dist(long long u, long long v) {
  return h[v] + h[u] - 2 * h[lca(u, v)];
}
void UPDATE(long long v) {
  long long u = v;
  while (u != 0) {
    dp[u] = min(dp[u], dist(u, v));
    u = pr[u];
  }
}
long long GET(long long v) {
  long long ans = +INF;
  long long u = v;
  while (u != 0) {
    ans = min(ans, dp[u] + dist(u, v));
    u = pr[u];
  }
  return ans;
}
void dfs(long long v, long long p = -1) {
  for (long long u : adj[v])
    if (u != p) par[0][u] = v, h[u] = h[v] + 1, dfs(u, v);
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
  ;
  long long m;
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) dp[i] = +INF;
  for (long long i = 0; i < n - 1; i++) {
    long long u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  CentroidDecomposition(1);
  dfs(1);
  for (long long j = 1; j < mlog; j++)
    for (long long i = 1; i <= n; i++) par[j][i] = par[j - 1][par[j - 1][i]];
  UPDATE(1);
  while (m--) {
    long long t;
    cin >> t;
    if (t == 1) {
      long long v;
      cin >> v;
      UPDATE(v);
    }
    if (t == 2) {
      long long v;
      cin >> v;
      cout << GET(v) << "\n";
    }
  }
  return 0;
}
