struct HLDecomposition {
  int n;
  vector<vector<int>> es;
  vector<int> par;
  vector<int> dep;
  vector<int> head;
  vector<int> next;
  vector<int> vid;
  HLDecomposition(int n)
    : n(n), es(n), par(n), dep(n), head(n), next(n, -1), vid(n) {}
  void add_edge(int v, int u) {
    es[v].push_back(u);
    es[u].push_back(v);
  }
  int dfs(int v = 0, int d = 0, int p = -1) {
    if (p != -1) par[v] = p;
    dep[v] = d;
    int mx = 0;
    int cnt = 1;
    for (int u : es[v]) {
      if (u == p) continue;
      int c = dfs(u, d + 1, v);
      cnt += c;
      if (mx < c) mx = c, next[v] = u;
    }
    return cnt;
  }
  void bfs(int v = 0) {
    int k = 0;
    queue<int> q;
    q.emplace(v);
    while (!q.empty()) {
      int h = q.front(); q.pop();
      for (int v = h; v != -1; v = next[v]) {
        vid[v] = k++;
        head[v] = h;
        for (int u : es[v]) {
          if (u == par[v] || u == next[v]) continue;
          q.push(u);
        }
      }
    }
  }
  void build() {
    dfs();
    bfs();
  }
  int lca(int v, int u) {
    while (true) {
      if (vid[u] > vid[v]) swap(u, v);
      if (head[u] == head[v]) return u;
      v = par[head[v]];
    }
  }
};