蒟蒻写过很多树剖题了，但卡了这么久了的还是第一个。

大概思路：线段树两个标记，一个维护当前区间有没有黑点（标记为1），否则为0.第二个标记则维护最靠左的那个黑点的编号，如果没有黑点则为inf。

然后我就boom 0 了。

#include <bits/stdc++.h>
using namespace std;
#define N 100010

template <class T>
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){
		if(c == '-') s = -1;
		c = getchar();
	}
	while(isdigit(c)){
		x = x * 10 + (c ^ '0');
		c = getchar();
	}
	a = x * s;
	return ;
}

struct node{
	int v, next;
	
	node(int v = 0, int next = 0){
		this -> v = v;
		this -> next = next;
		return ;
	}
	
} t[N << 1];
int f[N];
int n, Q;

int bian = 0;
inline void add(int u, int v){
	t[++bian] = node(v, f[u]), f[u] = bian;
	t[++bian] = node(u, f[v]), f[v] = bian;
	return ;
}

int top[N], fa[N], deth[N], son[N], siz[N];
int dfn[N], id = 0, rev[N];

#define v t[i].v
void dfs1(int now, int father){
	siz[now] = 1;
	fa[now] = father;
	deth[now] = deth[father] + 1;
	for(int i = f[now]; i; i = t[i].next){
		if(v != father){
			dfs1(v, now);
			siz[now] += siz[v];
			if(siz[v] > siz[son[now]])
				son[now] = v;
		}
	}
	return ;
}

void dfs2(int now, int tp){
	top[now] = tp;
	dfn[now] = ++id;
	rev[id] = now;
	if(!son[now]) return ;
	dfs2(son[now], tp);
	for(int i = f[now]; i; i = t[i].next){
		if(v != fa[now] && v != son[now])
			dfs2(v, v);
	}
	return ;
}
#undef v

const int inf = (int)2e9;
struct tree{
	int w, front;
	
	tree(int w = 0, int front = inf){
		this -> w = w;
		this -> front = front;
		return ;
	}
	
} e[N << 2];


inline void pushup(int o){
	e[o].w = max(e[o << 1].w, e[o << 1 | 1].w);
	if(!e[o].w) e[o].front = inf;  // no black point
	else if(e[o << 1].front != inf) e[o].front = e[o << 1].front;
	else if(e[o << 1 | 1].front != inf) e[o].front = e[o << 1 | 1].front;
	return ;
}

void build(int o, int l, int r){
	if(l == r){
		e[o].w = 0;
		e[o].front = inf;
		return ;
	}
	int mid = l + r >> 1;
	build(o << 1, l, mid);
	build(o << 1 | 1, mid + 1, r);
	pushup(o);
	return ;
}

void update(int o, int l, int r, int x){
	if(l > x || r < x) return ;
	if(l == r && l == x){
		e[o].w ^= 1;
		if(e[o].w) e[o].front = l;
		else e[o].front = inf;
		return ;
	}
	int mid = l + r >> 1;
	update(o << 1, l, mid, x);
	update(o << 1 | 1, mid + 1, r, x);
	pushup(o);
	return ;
}

int query(int o, int l, int r, int in, int end){
	if(l > end || r < in) return inf;
	if(l >= in && r <= end){
		return e[o].front;
	}
	int mid = l + r >> 1;
	int lson = query(o << 1, l, mid, in, end);
	int rson = query(o << 1 | 1, mid + 1, r, in, end);
	if(lson != inf) return lson;
	else return rson;
}

int ask_min(int x, int y){
	int sum = inf;
	while(top[x] != top[y]){
		if(deth[top[x]] < deth[top[y]]) swap(x, y);
		int temp = query(1, 1, n, dfn[top[x]], dfn[x]);
		if(temp != inf) sum = temp;
		x = fa[top[x]];
	}
	if(deth[x] > deth[y]) swap(x, y);
	int temp = query(1, 1, n, dfn[x], dfn[y]);
	if(temp != inf)
		sum = temp;
	return sum == inf ? -1 : dfn[sum];
}

int main(){
//	freopen("hh.txt", "r", stdin);
	read(n), read(Q);
	for(int i = 1; i < n; i++){
		int x, y;
		read(x), read(y);
		add(x, y);
	}
	dfs1(1, 0);
	dfs2(1, 0);
	build(1, 1, n);
	while(Q--){
		int flag, x, ans;
		read(flag);
		switch (flag){
			case 0:
				read(x);
				update(1, 1, n, dfn[x]);
				break;
			case 1:
				read(x);
				printf("%d\n", ask_min(1, x));
 		}
	}
	return 0;
}