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 XxXxmaxn = 100010;
struct XxXxedge {
  int XxXxto, XxXxnext;
} XxXxe[(0x1a9d + 379 - 0x1c16) * XxXxmaxn];
struct XxXxanc_node {
  int id;
  int XxXxdis;
  XxXxanc_node(int id, int XxXxdis) : id(id), XxXxdis(XxXxdis) {}
};
int XxXxn, XxXxm;
int XxXxsz[XxXxmaxn];
int XxXxhead[XxXxmaxn];
int XxXxecnt;
int XxXxrest;
int XxXxnearest[XxXxmaxn];
int XxXxlargest[XxXxmaxn];
int XxXxroot;
int XxXxdel[XxXxmaxn];
vector<XxXxanc_node> XxXxcentr_anc[XxXxmaxn];
int XxXxvis_node[XxXxmaxn];
int XxXxvcnt;
bool XxXxvis[XxXxmaxn];
int XxXxq[XxXxmaxn][(0xd21 + 5267 - 0x21b2)];
void XxXxadd_edge(int XxXxu, int XxXxv) {
  XxXxe[XxXxecnt].XxXxto = XxXxv;
  XxXxe[XxXxecnt].XxXxnext = XxXxhead[XxXxu];
  XxXxhead[XxXxu] = XxXxecnt++;
}
void init() {
  XxXxecnt = (0xf56 + 6039 - 0x26ed);
  memset(XxXxhead, -(0x1ec + 2671 - 0xc5a),
         sizeof(int) * (XxXxn + (0x9a2 + 3892 - 0x18d5)));
  for (int XxXxi = (0x15f6 + 292 - 0x171a); XxXxi <= XxXxn; XxXxi++)
    XxXxnearest[XxXxi] = 100010;
  for (int XxXxi = (0xc78 + 6041 - 0x2411); XxXxi <= XxXxn; XxXxi++)
    XxXxcentr_anc[XxXxi].clear();
}
void XxXxdoglike(int XxXxu) {
  int XxXxv;
  int(*st)[(0x1986 + 3165 - 0x25e1)] = XxXxq;
  int XxXxtp = (0x640 + 4536 - 0x17f8);
  int XxXxfa;
  ++XxXxtp;
  st[XxXxtp][(0x575 + 1635 - 0xbd8)] = XxXxu;
  st[XxXxtp][(0x1c7 + 463 - 0x395)] = XxXxhead[XxXxu];
  XxXxsz[XxXxu] = (0x1158 + 2081 - 0x1978);
  XxXxlargest[XxXxu] = (0x62b + 994 - 0xa0d);
  while (XxXxtp > (0x1170 + 2903 - 0x1cc7)) {
    XxXxu = st[XxXxtp][(0x16d9 + 140 - 0x1765)];
    XxXxfa =
        XxXxtp > (0xed9 + 3533 - 0x1ca6)
            ? st[XxXxtp - (0x1cd1 + 1890 - 0x2432)][(0xae9 + 4120 - 0x1b01)]
            : -(0xd9b + 1170 - 0x122c);
    int& XxXxi = st[XxXxtp][(0xd1d + 3951 - 0x1c8b)];
    if (XxXxi == -(0x79d + 2698 - 0x1226)) {
      XxXxlargest[XxXxu] = max(XxXxlargest[XxXxu], XxXxrest - XxXxsz[XxXxu]);
      if (XxXxroot == -(0x9d9 + 3491 - 0x177b) ||
          XxXxlargest[XxXxu] < XxXxlargest[XxXxroot])
        XxXxroot = XxXxu;
      --XxXxtp;
      if (XxXxfa != -(0x6ca + 4187 - 0x1724)) {
        XxXxsz[XxXxfa] += XxXxsz[XxXxu];
        XxXxlargest[XxXxfa] = max(XxXxlargest[XxXxfa], XxXxsz[XxXxu]);
      }
    } else {
      XxXxv = XxXxe[XxXxi].XxXxto;
      XxXxi = XxXxe[XxXxi].XxXxnext;
      if (XxXxv == XxXxfa || XxXxdel[XxXxv]) {
        continue;
      }
      ++XxXxtp;
      st[XxXxtp][(0xb48 + 158 - 0xbe6)] = XxXxv;
      st[XxXxtp][(0x36f + 5246 - 0x17ec)] = XxXxhead[XxXxv];
      XxXxsz[XxXxv] = (0x1b7b + 1379 - 0x20dd);
      XxXxlargest[XxXxv] = (0xb2f + 2786 - 0x1611);
    }
  }
}
void XxXxget_dis(int XxXxu) {
  int front = (0xcf2 + 3039 - 0x18d1), XxXxrear = (0x722 + 7434 - 0x242c);
  XxXxq[XxXxrear][(0x4e0 + 1879 - 0xc37)] = XxXxu;
  XxXxq[XxXxrear++][(0x1085 + 2784 - 0x1b64)] = (0x791 + 2663 - 0x11f8);
  XxXxvcnt = (0x486 + 5654 - 0x1a9c);
  XxXxvis[XxXxu] = (0x1914 + 2876 - 0x244f);
  XxXxvis_node[XxXxvcnt++] = XxXxu;
  int XxXxv, XxXxd;
  while (front < XxXxrear) {
    XxXxu = XxXxq[front][(0x9fc + 5248 - 0x1e7c)];
    XxXxd = XxXxq[front++][(0x13c4 + 2554 - 0x1dbd)];
    XxXxcentr_anc[XxXxu].push_back(XxXxanc_node(XxXxroot, XxXxd));
    for (int XxXxi = XxXxhead[XxXxu]; ~XxXxi; XxXxi = XxXxe[XxXxi].XxXxnext) {
      XxXxv = XxXxe[XxXxi].XxXxto;
      if (XxXxvis[XxXxv] || XxXxdel[XxXxv]) continue;
      XxXxq[XxXxrear][(0x494 + 1838 - 0xbc2)] = XxXxv;
      XxXxq[XxXxrear++][(0x9a9 + 7475 - 0x26db)] =
          XxXxd + (0xb7a + 871 - 0xee0);
      XxXxvis[XxXxv] = (0xe81 + 959 - 0x123f);
      XxXxvis_node[XxXxvcnt++] = XxXxv;
    }
  }
  for (int XxXxi = (0xfdf + 2830 - 0x1aed); XxXxi < XxXxvcnt; XxXxi++)
    XxXxvis[XxXxvis_node[XxXxi]] = (0x1285 + 3264 - 0x1f45);
}
void XxXxewqrij(int XxXxu) {
  int XxXxv;
  XxXxget_dis(XxXxu);
  XxXxdel[XxXxu] = (0x86c + 929 - 0xc0c);
  for (int XxXxi = XxXxhead[XxXxu]; ~XxXxi; XxXxi = XxXxe[XxXxi].XxXxnext) {
    XxXxv = XxXxe[XxXxi].XxXxto;
    if (XxXxdel[XxXxv]) continue;
    XxXxroot = -(0x1d6 + 4600 - 0x13cd);
    XxXxrest = XxXxsz[XxXxv];
    XxXxdoglike(XxXxv);
    XxXxewqrij(XxXxroot);
  }
}
void XxXxchange(int XxXxu) {
  int XxXxr;
  for (int XxXxi = (0x8aa + 2055 - 0x10b1); XxXxi < XxXxcentr_anc[XxXxu].size();
       XxXxi++) {
    XxXxr = XxXxcentr_anc[XxXxu][XxXxi].id;
    XxXxnearest[XxXxr] =
        min(XxXxnearest[XxXxr], XxXxcentr_anc[XxXxu][XxXxi].XxXxdis);
  }
}
int XxXxask(int XxXxu) {
  int XxXxr;
  int XxXxans = 100010;
  for (int XxXxi = (0x2c7 + 3912 - 0x120f); XxXxi < XxXxcentr_anc[XxXxu].size();
       XxXxi++) {
    XxXxr = XxXxcentr_anc[XxXxu][XxXxi].id;
    XxXxans =
        min(XxXxans, XxXxcentr_anc[XxXxu][XxXxi].XxXxdis + XxXxnearest[XxXxr]);
  }
  return XxXxans;
}
int main() {
  scanf("\x25\x64\x25\x64", &XxXxn, &XxXxm);
  init();
  int XxXxu, XxXxv;
  for (int XxXxi = (0x19e5 + 606 - 0x1c42); XxXxi < XxXxn; XxXxi++) {
    scanf("\x25\x64\x25\x64", &XxXxu, &XxXxv);
    XxXxadd_edge(XxXxu, XxXxv);
    XxXxadd_edge(XxXxv, XxXxu);
  }
  XxXxroot = -(0x18dd + 2983 - 0x2483);
  XxXxrest = XxXxn;
  XxXxdoglike((XxXxn + (0xe36 + 5256 - 0x22bd)) / (0x70c + 5582 - 0x1cd8));
  XxXxewqrij(XxXxroot);
  XxXxchange((0xf9a + 2325 - 0x18ae));
  int XxXxq, XxXxx;
  for (int XxXxi = (0xe03 + 3508 - 0x1bb7); XxXxi < XxXxm; XxXxi++) {
    scanf("\x25\x64\x25\x64", &XxXxq, &XxXxx);
    if (XxXxq == (0x21b0 + 1332 - 0x26e3)) {
      XxXxchange(XxXxx);
    } else {
      printf(
          "\x25\x64"
          "\n",
          XxXxask(XxXxx));
    }
  }
  return (0xabd + 2638 - 0x150b);
}
