// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
#include "../../src/alfred/config/fast-io.hpp"
#include "../../src/alfred/config/io-sync-off.hpp"
#include <iostream>
int n, k, c, q, u, v;
std::vector<int> G[100010];
#include "../../src/alfred/graph/lca.hpp"
int main(int argc, char const *argv[]) {
optimizeIO(), fast_read(n);
for (int i = 0; i < n; i++) {
fast_read(k);
while (k--) {
fast_read(c);
G[i].push_back(c);
}
}
LCA.init(n, 0);
fast_read(q);
while (q--) {
fast_read(u, v);
writeln(LCA.LCA(u, v));
}
return 0;
}
#line 1 "verify/verify-aizu-graph/aizu-lca.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
#line 1 "src/alfred/config/fast-io.hpp"
#include <iostream>
class FastIO {
private:
int siz = 100000;
char *buf, *p1, *p2;
public:
inline char nc(void) {
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, siz, stdin), p1 == p2) ? EOF : *p1++;
}
inline void pc(char c) { putchar(c); }
FastIO(void) { buf = (char *)malloc(siz); }
FastIO(int n) : siz(n) { buf = (char *)malloc(siz); } // n characters.
~FastIO(void) { free(buf); }
inline void resize(int n) {
siz = n;
buf = (char *)realloc(buf, siz);
}
} __buf;
inline void reset_size(int siz) {
__buf.resize(siz);
}
template <class T>
inline void fast_read(T &x) {
x = 0;
static char c = __buf.nc();
while (c < '0' || c > '9') c = __buf.nc();
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48), c = __buf.nc();
}
}
template <class T>
inline void write(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar((x % 10) ^ 48);
}
template <class T>
inline void writeln(T x) {
write(x), puts("");
}
template <typename T, typename... V>
inline void writeln(T x, V... v) {
write(x), putchar(' '), writeln(v...);
}
template <typename T, typename... V>
inline void fast_read(T &t, V &...v) {
fast_read(t), fast_read(v...);
}
#line 1 "src/alfred/config/io-sync-off.hpp"
#include <bits/stdc++.h>
inline void optimizeIO(void) {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL), std::cout.tie(NULL);
}
#line 6 "verify/verify-aizu-graph/aizu-lca.test.cpp"
int n, k, c, q, u, v;
std::vector<int> G[100010];
#line 1 "src/alfred/graph/lca.hpp"
#line 1 "src/alfred/data_structure/sparse-table.hpp"
#line 7 "src/alfred/data_structure/sparse-table.hpp"
template <class T>
struct MaxInfo {
T val;
MaxInfo(void) { val = std::numeric_limits<T>::min(); }
template <class InitT>
MaxInfo(InitT x) { val = x; }
MaxInfo operator+(MaxInfo &x) {
return {std::max(val, x.val)};
}
};
template <class T>
struct MinInfo {
T val;
MinInfo(void) { val = std::numeric_limits<T>::max(); }
template <class InitT>
MinInfo(InitT x) { val = x; }
MinInfo operator+(MinInfo &x) {
return {std::min(val, x.val)};
}
};
template <class T>
struct GcdInfo {
T val;
GcdInfo(void) { val = T(); }
template <class InitT>
GcdInfo(InitT x) { val = x; }
GcdInfo operator+(GcdInfo &x) {
#if __cplusplus >= 201703L
return {std::gcd(x.val, val)};
#else
return {__gcd(x.val, val)};
#endif
}
};
template <class T>
class SparseTable {
private:
int n;
std::vector<std::vector<T>> ST;
public:
SparseTable(void) {}
SparseTable(int N) : n(N), ST(N, std::vector<T>(std::__lg(N) + 1)) {}
template <class InitT>
SparseTable(std::vector<InitT> &_init) : SparseTable(_init.size()) { init(_init, true); }
template <class InitT>
inline void init(std::vector<InitT> &_init, bool internal = false) {
if (!internal) {
n = _init.size();
ST.assign(n, std::vector<T>(std::__lg(n) + 1));
}
for (int i = 0; i < n; i++) ST[i][0] = T(_init[i]);
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 0; j + (1 << i) - 1 < n; j++) {
ST[j][i] = ST[j][i - 1] + ST[j + (1 << (i - 1))][i - 1];
}
}
}
inline T query(int l, int r) { // 0 based
if (l > r) return T();
int w = std::__lg(r - l + 1);
return ST[l][w] + ST[r - (1 << w) + 1][w];
}
inline T disjoint_query(int l, int r) {
if (l > r) return T();
T ans = T();
for (int i = std::__lg(r - l + 1); i >= 0; i--) {
if ((1 << i) <= r - l + 1) {
ans = ans + ST[l][i];
l += 1 << i;
}
}
return ans;
}
};
#line 6 "src/alfred/graph/lca.hpp"
// requires a previous graph definition.
class LCAImpl {
private:
std::vector<int> dfn, seq; // dfn and seq are (internally) zero indexed.
static std::vector<int> d;
struct EulerTourInfo {
int val;
EulerTourInfo(void) : val(0) {}
EulerTourInfo(int x) : val(x) {}
EulerTourInfo operator+(EulerTourInfo &x) {
return d[val] < d[x.val] ? val : x.val;
}
};
SparseTable<EulerTourInfo> lca; // 0 indexed.
inline void _dfs(int x, int fa) {
dfn[x] = seq.size();
seq.push_back(x), d[x] = d[fa] + 1;
for (auto &y : G[x]) {
if (y == fa) continue;
_dfs(y, x), seq.push_back(x);
}
}
public:
inline void init(int n, int rt = 1) {
d.assign(n + 1, 0), dfn.assign(n + 1, 0);
seq.clear(), _dfs(rt, 0), lca.init(seq);
}
inline int LCA(int u, int v) {
if (u == -1) return v;
if (v == -1) return u;
if (dfn[u] > dfn[v]) std::swap(u, v);
return lca.query(dfn[u], dfn[v]).val;
}
inline int dis(int u, int v) {
return d[u] + d[v] - 2 * d[LCA(u, v)];
}
} LCA;
std::vector<int> LCAImpl::d;
struct LCAInfo {
int val;
LCAInfo(void) : val(-1) {}
template <class InitT>
LCAInfo(InitT x) { val = x; }
LCAInfo operator+(LCAInfo &x) {
return {LCA.LCA(val, x.val)};
}
}; // for range lca.
#line 11 "verify/verify-aizu-graph/aizu-lca.test.cpp"
int main(int argc, char const *argv[]) {
optimizeIO(), fast_read(n);
for (int i = 0; i < n; i++) {
fast_read(k);
while (k--) {
fast_read(c);
G[i].push_back(c);
}
}
LCA.init(n, 0);
fast_read(q);
while (q--) {
fast_read(u, v);
writeln(LCA.LCA(u, v));
}
return 0;
}
verify/verify-aizu-graph/aizu-lca.test.cpp