# SPOJQTREE 3

Solução: Patrícia Hongo

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>

using namespace std;

#define MAXN 100023
#define ii pair<int, int>

vector<int> t[MAXN];

/* Obtem o RMQ em [a,b]; chamar com root=0, rl=0, rr=n-1 */
int query(int root, int rl, int rr, int a, int b, int ch) {
if (a > b) return -1;

if (rl==a && rr==b) return t[ch][root];
int rm = (rl+rr)/2;

int p1 = query(2*root+1, rl, rm, a, min(b, rm), ch);
int p2 = query(2*root+2, rm+1, rr, max(a, rm+1), b, ch);
if(p1 == -1 && p2 == -1) return -1;
else if(p1 == -1) return p2;
else if(p2 == -1) return p1;
return p2;
}
/* Muda posiao x para vx; chamar com root=0, rl=0, rr=n-1 */
void update(int root, int rl, int rr, int x, int vx, int a, int ch) {
if (rl==rr){
if(vx==1)
t[ch][root] = a;
else
t[ch][root] = -1;
}
else {
int rm = (rl+rr)/2;
if (x <= rm) update(2*root+1, rl, rm, x, vx, a, ch);
else update(2*root+2, rm+1, rr, x, vx, a, ch);
int p1 = t[ch][2*root+1];
int p2 = t[ch][2*root+2];
if(p1 == -1 && p2 == -1) t[ch][root] = -1;
else if(p1 == -1) t[ch][root] = p2;
else if(p2 == -1) t[ch][root] = p1;
else t[ch][root] = p2;
//t[ch][root] = max(t[ch][2*root+1], t[ch][2*root+2]);
}
}

vector<int> g[MAXN];
/* Vertice do topo da chain i, tam da chain i e qtd delas */
/* Chain do vErtice i e seu Indice nela (cresce pra raiz) */
int chain[MAXN], chidx[MAXN];
/* Altura do vertice i, seu antecessor e tam da suBarvore */
int depth[MAXN], pai[MAXN], size[MAXN];

/* Adiciona um vertice v no topo da chain c */
void chadd(int v, int c) {
chidx[v] = chsz[c]++;
chain[v] = c;
}

/* Gera as chains e vetores associados */
void dfshl(int x) {
size[x]=1;
for (int i = 0; i < g[x].size(); i++) {
int v = g[x][i];
if (pai[x] != v) {
depth[v] = depth[x]+1;
pai[v] = x;
dfshl(v);
size[x] += size[v];
}
}

chain[x] = -1;
for (int i = 0; i < g[x].size(); i++)
if (g[x][i] != pai[x] && size[g[x][i]] > size[x]/2)
if (chain[x] == -1) chadd(x, nch++);
}

int val[MAXN];
int chtr[MAXN], ntr = 0;

/* Exemplo de LCA. Percorre as chains no caminho entre a e b
Pode ser alterado para responder query usando uma estrutura
de dados de intervalos por chain (por ex. BIT, segtree) */

int LCA(int a, int b) {
int mm = 0x3f3f3f3f;
if(val[a] == 1) mm = a;
if(val[b] == 1) return 0;

while (chain[a] != chain[b]) {

// query chain[a] em [chidx[a], chsz[chain[a]]-1]
int x = query(0, 0, chsz[chain[a]]-1,
chidx[a], chsz[chain[a]]-1, chtr[chain[a]]);

if(x != -1)
mm = x;

if(val[a] == 1)
mm = a;
}
}
if (depth[a] < depth[b]) {
// query chain[a] em [chidx[b], chidx[a]]
int x = query(0, 0, chsz[chain[a]]-1,
chidx[b], chidx[a], chtr[chain[a]]);
if(x != -1) mm = x;
return mm;
}
// query chain[a] em [chidx[a], chidx[b]]
int x = query(0, 0, chsz[chain[a]]-1,
chidx[a], chidx[b], chtr[chain[a]]);
if(x != -1) mm=x;

return mm;
}

int n, q;

int main(){
int a, b, c;

scanf("%d %d", &n, &q);
nch=0;
memset(chsz,0,sizeof(chsz));
memset(val, 0, sizeof(val));
for (int i=0; i<n; i++)
g[i].clear();
for(int i = 0; i < n-1; ++i){
scanf("%d %d",&a,&b);
--a; --b;
g[a].push_back(b);
g[b].push_back(a);
}
dfshl(0);

for(int i = 0; i< nch; ++i){
chtr[i] = ntr;
t[ntr++].assign(4*(chsz[i]+2), -1);
}

while(q--){
scanf("%d %d", &c, &a);
--a;
if(c == 0){
val[a] = 1-val[a];
update(0, 0, chsz[chain[a]]-1, chidx[a], val[a], a, chtr[chain[a]]);
continue;
}
int rt = LCA(a, 0);
if(rt < 0x3f3f3f3f-5)
printf("%d\n", rt+1);
else printf("-1\n");
}

return 0;
}