1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
const int M = N * 2;
int n, m;
int head[N], to[M], nxt[M], tot;
void init() { tot = 0; memset(head, -1, sizeof(head)); }
void addedge(int x, int y) { to[tot] = y; nxt[tot] = head[x]; head[x] = tot++; }
const int DEP = 20;
int fa[N][DEP];
int dep[N];
void bfs(int rt) {
  queue<int> que; que.push(rt);
  dep[rt] = 0; fa[rt][0] = rt;
  while (!que.empty()) {
    int u = que.front(); que.pop();
    for (int i = 1; i < DEP; i++) { fa[u][i] = fa[fa[u][i - 1]][i - 1]; }
    for (int i = head[u]; ~i; i = nxt[i]) {
      int v = to[i];
      if (v != fa[u][0]) { dep[v] = dep[u] + 1; fa[v][0] = u; que.push(v); }
    }
  }
}
int queryLCA(int u, int v) {
  if (dep[u] > dep[v]) { swap(u, v); }
  for (int d = dep[v] - dep[u], i = 0; d; d >>= 1, i++) {
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX