Xenia and Tree

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

typedef long long ll;
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define all(x) x.begin(), x.end()
#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define fd(i,a,b) for(int i = (a); i >= (b); i--)
#define mp make_pair
#define faster_io() ios_base::sync_with_stdio(false)
#define pb push_back
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
#define vii vector<pair<int,int>>

const int INF = 1000000005;
const ll INFLL = 1000000000000000002ll;
const ll MOD = 1000000007;

inline ll min(ll a, ll b, ll c){return min(min(a,b),c);}
inline ll min(ll a, ll b, ll c, ll d){return min(min(min(a,b),c),d);}
inline ll max(ll a, ll b, ll c){return max(max(a,b),c);}
inline ll max(ll a, ll b, ll c, ll d){return max(max(max(a,b),c),d);}

// -------------------------------------------------------------------------------------------------------------

int N, Q, D[100005], Dist[100005], L[100005][18];
vector<int> E[100005], Red;

void dfs(int n, int p, int d)
{
    D[n] = d;
    L[n][0] = p;
    for(int v : E[n]) if(v != p) dfs(v,n,d+1);
}

int lca(int u, int v)
{
    if(D[u] < D[v]) return lca(v,u);
    int diff = D[u] - D[v];
    f(i,0,17) if(diff&(1<<i)) u = L[u][i];
    if(u == v) return u;
    fd(i,17,0) if(L[u][i] != L[v][i]) u = L[u][i], v = L[v][i];
    return L[u][0];
}

int dist(int u, int v)
{
    int l = lca(u,v);
    return D[u] - D[l] + D[v] - D[l];
}

void calc()
{
    f(i,1,N) Dist[i] = INF;
    queue<int> q;
    for(int v : Red) q.push(v), Dist[v] = 0;
    while(!q.empty())
    {
        int n = q.front();
        q.pop();

        for(int v : E[n]) if(Dist[n] + 1 < Dist[v])
        {
            q.push(v);
            Dist[v] = Dist[n] + 1;
        }
    }
}

int main()
{
    cin >> N >> Q;
    f(i,1,N-1)
    {
        int a,b;
        scanf("%d %d", &a, &b);
        E[a].pb(b), E[b].pb(a);
    }
    Red.pb(1);
    dfs(1,0,0);
    f(j,1,17) f(i,1,N) L[i][j] = L[L[i][j-1]][j-1];
    calc();
    vector<int> pend;
    f(q,1,Q)
    {
        int t,v;
        scanf("%d %d", &t, &v);
        if(t == 1)
        {
            pend.pb(v);
            if(SZ(pend) == 300)
            {
                for(int node : pend) Red.pb(node);
                pend.clear();
                calc();
            }
        }
        else
        {
            int ans = Dist[v];
            for(int u : pend) ans = min(ans, dist(u,v));
            printf("%d\n", ans);
        }
    }
}