#include <cstdio>
#define MN 130010

int M, N, first, sCnt, ary[MN*2];
char opt[10];

struct node {
 node *fa, *ch[2];
 int val, size;
 bool rev;
 void get(int,node*);
}s[MN*2], null, *root;

void node::get(int v, node *f) {
 val = v;
 fa = f;
 ch[0] = ch[1] = &null;
 size = 1;
 rev = false;
}

void pass(node *now) {
 static node *tmp;
 if(now == &null;) return;
 now->rev = false;
 tmp = now->ch[0]; now->ch[0] = now->ch[1]; now->ch[1] = tmp;
 now->ch[0]->rev ^= 1;
 now->ch[1]->rev ^= 1;
}

void rotate(node *now, int c) {
 static node *f;
 f = now->fa;
 if(f == &null;) return;
 if(now->rev == true) pass(now);
 f->ch[!c] = now->ch[c];
 if(now->ch[c] != &null;)
  now->ch[c]->fa = f;
 now->fa = f->fa;
 if(f->fa->ch[0] == f)
  f->fa->ch[0] = now;
 else f->fa->ch[1] = now;
 now->ch[c] = f;
 f->fa = now;
 now->size = f->size;
 f->size -= (now->ch[!c]->size + 1);
 if(f == root) root = now;
}

void splay(node *now, node *tar) {
 static node *nf, *nff;
 while(now->fa!=tar) {
  nf = now->fa;
  if(nf->fa == tar)
   rotate(now, nf->ch[0]==now);
  else {
   nff = nf->fa;
   if(nff->ch[0]==nf) {
    if(nf->ch[0]==now) {
     rotate(nf, 1);
     rotate(now, 1);
    } else {
     rotate(now, 0);
     rotate(now, 1);
    }
   } else {
    if(nf->ch[1]==now) {
     rotate(nf, 0);
     rotate(now, 0);
    } else {
     rotate(now, 1);
     rotate(now, 0);
    }
   }
  }
 }
}

node* cons(int lb, int rb, node *f) {
 if(lb > rb) return &null;
 int mid = (lb+rb)/2, nc = sCnt++;
 s[nc].get(ary[mid], f);
 s[nc].ch[0] = cons(lb, mid-1, &s[nc]);
 s[nc].ch[1] = cons(mid+1, rb, &s[nc]);
 s[nc].size += (s[nc].ch[0]->size + s[nc].ch[1]->size);
 return &s[nc];
}

node* find(int tar, node *f) {
 static node *now;
 now = root;
 while(true) {
  if(now->rev == true) pass(now);
  if(now->ch[0]->size == tar) break;
  if(now->ch[0]->size >= tar) {
   now = now->ch[0];
  } else {
   tar -= (now->ch[0]->size+1);
   now = now->ch[1];
  }
 }
 splay(now, f);
 return now;
}

void out(int a) {
 if(a==0 || a==N+1) return;
 if(!first) putchar(' ');
 else first = false;
 printf("%d", a);
}

void travel(node *now) {
 if(now == &null;) return;
 if(now->rev) {
  now->ch[0]->rev ^= 1;
  now->ch[1]->rev ^= 1;
  travel(now->ch[1]);
  out(now->val);
  travel(now->ch[0]);
 } else {
  travel(now->ch[0]);
  out(now->val);
  travel(now->ch[1]);
 }
}

void init() {
 null.val = -1;
 null.size = 0;
 null.ch[0] = null.ch[0] = null.fa = &null;
 root = cons(0, N+N, &null;);
}


//Doubling

std::vector<int> edge[MN];
int jump[MN][20], dp[MN], fa[MN], dep[MN];
int que[MN], ft, rr;

inline int ju(int pos, int len) {
    for(int i=19; i>=0; i--) {
        if((1<<i) <= len) {
            pos = jump[pos][i];
            len -= (1<<i);
        }
    }
    return pos;
}
1. BFS calculate dep
}
for(int i=1; i<=N; i++) jump[i][0] = fa[i];
for(int jp=1; jp<20; jp++)
    for(int i=1; i<=N; i++)
        jump[i][jp] = jump[jump[i][jp-1]][jp-1];

a = ju(a, dep[a]-dep[b]);
int lb = 0, rb = dep[a], mid;
while(lb < rb) {
    mid = (lb+rb)/2;
    if(ju(a, mid) == ju(b, mid)) rb = mid;
    else lb = mid+1;
}
int lca = ju(a, lb);