QTREE3 chi ashxatum

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <cmath>
#include <iostream>
using namespace std;
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define sqr(x) ((x)*(x))
#define ABS(x) (((x)>=0)?(x):-1*(x))
#define geti(x) scanf("%d", &x)
#define puti(x) printf("%d\n", x)
typedef double real;
typedef long long ll;
typedef pair<int,int> pt;
const int INF = 1000*1000*1000+7;
const long long INF64 = 1e18;
const real EPS = 1e-8;

const int MN = 100*1000+3;
const int NN = 100+3;
vector<int> T[MN];
vector<int> HW[MN];
int HP[MN];
int SZ[MN];
int HID[MN];
int DEP[MN];
int C[MN];
int P[MN][19];
void dfs(int v, int p=0){
	P[v][0] = p;
	DEP[v] = DEP[p]+1;
	for(int i=1;i<19;i++){
		P[v][i] = P[P[v][i-1]][i-1];
	}
	C[v] = 1;
	for(int i=0;i<T[v].size();i++){
		int to = T[v][i];
		if(to == P[v][0])continue;
		dfs(to,v);
		C[v]+=C[to];
	}
}
void heavy_dfs(int v,int heavy){
	HID[v] = heavy;
	for(int i=0;i<T[v].size();i++){
		int to = T[v][i];
		if(to == P[v][0])continue;
		if(C[to]*2 >= C[v]){
			dfs(to,heavy);
		}
		else{
			dfs(to,to);
		}
	}
	HW[heavy].push_back(v);
	HP[v] = SZ[HID[v]]++;
}
typedef struct item * pitem;
struct item{
	pitem l,r;
	set<int> S;
	item():l(NULL),r(NULL){}
};
item Q[4*MN];int nq;
pitem HPIT[MN];
void update(int id,pitem &v,int pos,int l=-1, int r=-1){
	if(l==-1){l=0;r=SZ[id]-1;}
	if(!v){ v = &Q[nq++];}

	if(v->S.find(-pos) != v->S.end()){
		v->S.erase(-pos);
	}
	else{
		v->S.insert(-pos);
	}

	if(l==r){
		return;
	}
	int m = (l+r)/2;
	if(m >= pos){
		update(id,v->l,pos,l,m);
	}
	else{
		update(id,v->r,pos,m+1,r);
	}
}

int query(int id,pitem v, int ql,int qr,int l=-1, int r=-1){
	if(l==-1){l=0;r=SZ[id]-1;}
	if(!v){ return INF;}
	if(ql>qr){return INF;}
	if(ql==l && qr == r){
		if(v->S.size()==0){
			return INF;
		}
		return *(v->S.begin());
	}
	int m = (l+r)/2;
	return min(query(id,v->l,ql,min(qr,m),l,m),query(id,v->r,max(ql,m+1),qr,m+1,r));
}
int get(int f){
	int minv = -1;
	for(;DEP[f] >= DEP[1];){
		int v = HID[f];
		int ret = -query(v,HPIT[v],HP[f],HP[v]);
		if(ret!= -INF){
			if(minv == -1 || DEP[minv] > DEP[ HW[v][ret] ]){
				minv = HW[v][ret];
			}
		}
		f = P[v][0];
	}
	return minv;
}
void solve(){
	nq = 0;
	int n,q;
	geti(n);geti(q);
	for(int i=0;i<n-1;i++){
		int a,b;
		geti(a);geti(b);
		T[a].push_back(b);
		T[b].push_back(a);
	}
	dfs(1);
	heavy_dfs(1,1);
	for(int i=0;i<q;i++){
		int cmd,b;
		geti(cmd);geti(b);
		if(cmd == 1){
			//printf("%d\n", get(b));
		}
		else{
			update(HID[b],HPIT[HID[b]],HP[b]);
		}
	}
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	solve();
	return 0;
}