// Tarjan's off-line least common ancestors
// See CLRS, 2nd ed, p.521, problem 21-3
// Assumes order of siblings is irrelevant
// BPW 1/12/03

#include <stdio.h>
#include <stdlib.h>

#define WHITE (0)
#define BLACK (1)

// Tree structure
int n,root,*firstChild,*rightSibling,*treeParent,*color;

// P - pairs to find LCA for
// Psize = number of pairs
// uP = first vertex, vP = second vertex, firstPair[i]=first pair with
//                                        i as uP
int Psize,*uP,*vP,*firstPair;

// Union-find structure for vertices of tree
int *parent,*weight,numTrees;

// For LCA function
int *ancestor;

void readTree()
{
int i,k,kParent;

scanf("%d",&n);
firstChild=(int*) malloc(n*sizeof(int));
rightSibling=(int*) malloc(n*sizeof(int));
treeParent=(int*) malloc(n*sizeof(int));
color=(int*) malloc(n*sizeof(int));
if (!firstChild || !rightSibling || !treeParent || !color)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
for (i=0;i<n;i++)
{
  color[i]=BLACK;
  firstChild[i]=rightSibling[i]=(-1);
}
for (i=0;i<n-1;i++)
{
  scanf("%d %d",&k,&kParent);
  if (k<0 || k>=n || kParent<0 || kParent>=n || color[k]==WHITE)
  {
    printf("Input error %d\n",__LINE__);
    exit(0);
  }
  treeParent[k]=kParent;
  color[k]=WHITE;
  rightSibling[k]=firstChild[kParent];
  firstChild[kParent]=k;
}
root=(-1);
for (i=0;i<n;i++)
  if (color[i]==BLACK)
    if (root==(-1))
    {
      root=i;
      color[root]=WHITE;
    }
    else
    {
      printf("Root error %d\n",__LINE__);
      exit(0);
    }
treeParent[root]=(-1);
printf("debug - root is %d\n",root);
printf(" i   firstChild  rightSibling treeParent\n");
for (i=0;i<n;i++)
  printf("%3d     %3d         %3d         %3d\n",
    i,firstChild[i],rightSibling[i],treeParent[i]);

parent=(int*) malloc(n*sizeof(int));
weight=(int*) malloc(n*sizeof(int));
ancestor=(int*) malloc(n*sizeof(int));
if (!parent || !weight || !ancestor)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
for (i=0;i<n;i++)
{
  parent[i]=i;
  weight[i]=1;
}
numTrees=n;
}

int find(int x)
{
int i,j,root;

for (i=x;
     parent[i]!=i;
     i=parent[i])
  ;
root=i;
/* path compression */
for (i=x;
     parent[i]!=i;
     j=parent[i],parent[i]=root,i=j)
  ;
return root;
}

void makeEquivalent(int x,int y)
{
int i,j;

i=find(x);
j=find(y);
if (i==j)
  return;

// union-by-weight
if (weight[i]>weight[j])
{
  parent[j]=i;
  weight[i]+=weight[j];
}
else
{
  parent[i]=j;
  weight[j]+=weight[i];
}
numTrees--;
}

void readP()
{
int i,j;

scanf("%d",&Psize);
firstPair=(int*) malloc((n+1)*sizeof(int));
uP=(int*) malloc(Psize*sizeof(int));
vP=(int*) malloc(Psize*sizeof(int));
if (!firstPair || !uP || !vP)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
// Pairs {x,y} must be sorted lexicographically
// and are expected to be available symmetrically,
// i.e. (x,y) and (y,x)
for (i=0;i<Psize;i++)
  scanf("%d %d",&uP[i],&vP[i]);
// Check input order
for (i=1;i<Psize;i++)
  if (uP[i-1]>uP[i] || (uP[i-1]==uP[i] && vP[i-1]>vP[i]))
  {
    printf("Input order error %d\n",__LINE__);
    exit(0);
  }

j=0;
for (i=0; i<n; i++)
{
  firstPair[i]=j;
  for ( ;
       j<Psize && uP[j]==i;
       j++)
    ;
}
firstPair[n]=Psize;
}

void LCA(int u)
{
int v,i;

ancestor[find(u)]=u;
for (v=firstChild[u];
     v!=(-1);
     v=rightSibling[v])
{
  LCA(v);
  makeEquivalent(u,v);
  ancestor[find(u)]=u;
}
if (color[u]==BLACK)
{
  printf("error at %d\n",__LINE__);
  exit(0);
}
color[u]=BLACK;
// for each node v such that {u,v} is in P and v is black
//   report LCA
for (i=firstPair[u];
     i<firstPair[u+1];
     i++)
{
  v=vP[i];
  if (color[v]==BLACK)
    printf("The LCA of %d and %d is %d\n",u,v,ancestor[find(v)]);
}
}

main()
{

readTree();
readP();
LCA(root);
}