{-# LANGUAGE BangPatterns #-}

import Control.Monad
import Data.Array
import Data.Bits
import qualified Data.ByteString.Char8 as C
import Data.Graph (buildG, dff, Vertex)
import Data.Maybe
import Data.List
import Data.Tree (levels)

main = readLn >>= \n -> join $ sub n <$> replicateM n get

sub n bs = readLn >>= \q -> sol n bs <$> replicateM q get >>= put

get = fmap fst . mapMaybe C.readInt . C.words <$> C.getLine

put = mapM_ print

sol n bs = fmap (\[u,v] -> lca u v)
  where
  -- vertex indices
  as = [0..n-1] :: [Vertex]

  -- graph as a tree
  g = buildG (0,n-1) . join $ zipWith (\a b -> fmap ((,) a) (tail b)) as bs

  -- root lookups (assume (-1) as a parent of the tree root 0)
  rt = array (0,n-1) $ dfs (-1) [] 0
    where
    dfs w ps u = (u,w):foldl' (dfs u) ps (g!u)

  -- vertex levels by using Data.Graph.dff and Data.Tree.levels
  -- dff: a spanning forest by DFS starting from each vertex
  -- levels: the list of nodes at each level of the tree 
  lvs = array (0,n-1) . sort
    . concat . zipWith (fmap . flip (,)) [1..]
    . concat . fmap levels $ dff g :: Array Vertex Int

  -- Lowest Common Ancestor (LCA) by binary search
  lca !u !v
    | u == v        = u
    | lvs!u > lvs!v = lca (rtk j u) v
    | lvs!u < lvs!v = lca u (rtk j v)
    | otherwise     = lca u' v'
    where
    j = logBase2 $ abs (lvs!u - lvs!v)
    (u',v') = loop (logBase2 n) (u,v)
    loop k (x,y)
      | k==0      = (x',y')
      | x'/=y'    = (x',y')
      | otherwise = loop (k `div` 2) (x,y)
      where
      x' = rtk k x
      y' = rtk k y

  -- (2^k)-th parent lookups : TBD memoize
  rtk 0 = (rt!)
  rtk k = rtk (k-1) . rtk (k-1)

  -- leading bit position
  logBase2 x = finiteBitSize x - countLeadingZeros x - 1

