<LCA> Template

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

#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair <int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vpii vector<pii>

#define read1(a) int a; scanf("%d", &a)
#define read2(a, b) int a, b; scanf("%d %d", &a, &b)
#define read3(a, b, c) int a, b, c; scanf("%d %d %d", &a, &b, &c)

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)

#define readgi(n) F0R(i, n) { scanf("%d", &arr[i]); }
#define readgs(n) F0R(i, n) { scanf(" %c", &arr[i]); }

#define f first
#define s second

#define usaco(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout);

#define println1(a) printf("%d\n", a);
#define println2(a, b) printf("%d %d\n", a, b);
#define println3(a, b, c) printf("%d %d %d\n", a, b, c);
#define pv(v) for (int i : v) { printf("%d ", i); } printf("\n");

const int MOD = 1000000007;
const int MAX = 100005;
const int N = 18;
int arr[MAX];

vector<int> g[MAX];
int depth[MAX];
int par[MAX][N];

void dfs(int st, int p) {
    par[st][0] = p;
    for (int i : g[st]) {
        if (i == p) { continue; }
        depth[i] = depth[st] + 1;
        dfs(i, st);
    }
}

void init() {
    FOR(j, 1, N) { F0R(i, MAX) {
        if (1<<(j) > depth[i]-1) { continue; }
        par[i][j] = par[par[i][j-1]][j-1];
    }}
}

int anc(int x, int y) {
    /* yth ancestor of x */
    for (int i=N-1; i>=0; i--) { if ((1<<i)<=y) { x = par[x][i]; y -= (1<<i); } }
    return x;
}

int lca(int x, int y) {
    if (depth[x] < depth[y]) { swap(x, y); }
    for (int i = N-1; i >= 0; i--) {
        if (depth[par[x][i]] >= depth[y]) { x = par[x][i]; }
    }
    if (x == y) { return x; }
    for (int i=N-1; i>=0; i--) {
        if (par[x][i] != par[y][i]) { x = par[x][i]; y = par[y][i]; }
    }
    return par[x][0];
}

int main() {
    depth[1] = 1;
    dfs(1, -1); init();
}