output_description: For each query, print the LCA of u and v in a line.
input_description: n
      k0 c1 c2 ... ck0
      k1 c1 c2 ... ck1
      :
      kn-1 c1 c2 ... ckn-1
      q
      u1 v1
      u2 v2
      :
      uq vq
      
  
  The first line of the input includes an integer n, the number of nodes of the
  tree.
  
  In the next n lines, the information of node i is given. ki is the number of
  children of node i, and c1, ... cki are node IDs of 1st, ... kth child of node
  i.
  
  In the next line, the number of queryies q is given. In the next q lines,
  pairs of u and v are given as the queries.
attempt: from collections import defaultdict
  
  
  class Tree:
      def __init__(self, N):
          self.N = N
          self.D = (self.N - 1).bit_length()
          self.E = defaultdict(dict)
  
      def add_edge(self, init, end, weight, undirected=False):
          self.E[init][end] = weight
          if undirected:
              self.E[end][init] = weight
  
      def dfs(self, root):
          # parents[v]: the parent of the vertex v
          # depth[v]: the depth of the vertex v from the root
          # dist[v]: the distance of the vertex v from the root.
          self.parent = [None] * self.N
          self.depth = [-1] * self.N
          self.dist = [float("inf")] * self.N
          self.parent[root] = -1
          self.depth[root] = 0
          self.dist[root] = 0
          stack = [root]
          while stack:
              v = stack.pop()
              for u in self.E[v].keys():
                  if self.depth[u] != -1:
                      continue
                  self.parent[u] = v
                  self.depth[u] = self.depth[v] + 1
                  self.dist[u] = self.dist[v] + self.E[v][u]
                  stack.append(u)
  
      def doubling(self):
          # O(N log N) time
          self.next = [self.parent]
          for d in range(1, self.D):
              self.next.append(
                  [
                      (
                          self.next[d - 1][self.next[d - 1][v]]
                          if self.next[d - 1][v] != -1
                          else -1
                      )
                      for v in range(self.N)
                  ]
              )
  
      def lca(self, u, v):
          # O(log N) time
          # the depth of v is set to be no less than that of u
          if self.depth[u] > self.depth[v]:
              u, v = v, u
          # find the ancestor of v with the same depth as that of u
          diff = self.depth[v] - self.depth[u]
          for i in range(diff.bit_length()):
              if diff & 1:
                  v = self.next[i][v]
              diff >>= 1
          if u == v:
              return u
          for i in range(self.D - 1, -1, -1):
              pu, pv = self.next[i][u], self.next[i][v]
              if pu != pv:
                  u, v = pu, pv
          return self.next[0][u]
  
  
  n = int(input())
  tr = Tree(n)
  for i in range(n):
      (
          k,
          *C,
      ) = map(int, input().split())
      for c in C:
          tr.add_edge(i, c, 1, undirected=True)
  tr.dfs(0)
  tr.doubling()
  q = int(input())
  for _ in range(q):
      u, v = map(int, input().split())
      print(tr.lca(u, v))
  
problem_description: LCA: Lowest Common Ancestor
  
  For a rooted tree, find the lowest common ancestor of two nodes u and v.
  
  The given tree consists of n nodes and every node has a unique ID from 0 to
  n-1 where 0 is the root.
samples: [{"input": "8\n    3 1 2 3\n    2 4 5\n    0\n    0\n    0\n    2 6 7\n    0\n    0\n    4\n    4 6\n    4 7\n    4 3\n    5 2", "output": "1\n    1\n    0\n    0"}]