Problema C - A caminho da seleção

O Francisco obteve uma excelente pontuação na final das ONI e por isso vai poder competir na prova de seleção, para concorrer por um lugar na equipa portuguesa na IOI. Por isso, o Francisco já tem marcada uma viagem de comboio de sua casa até ao local da prova.

A rede de estações de comboio de Portugal tem N estações e N - 1 ligações entre estações (cada ligação consiste numa única linha bidirecional que liga apenas duas estações) tal que é possível ir de qualquer estação até qualquer outra apenas usando as ligações. O Francisco vai viajar da estação A para a estação B.

O Francisco tem algum tempo extra na viagem, e gostaria de visitar um monumento conhecido que está situado perto de uma estação. Infelizmente essa estação não está necessariamente entre as duas estações, por isso terá de mudar de comboio a certa altura. Após olhar para o mapa, o Francisco não conseguiu ver qual era e precisa da tua ajuda para não se perder. Dada a estação perto da qual se encontra o monumento consegues determinar onde é que o Francisco tem de mudar de linha? (Ou seja, a estação no caminho de A para B mais próxima da dada).

Imaginem, por exemplo, que temos N = 7 estações com as ligações ilustradas na imagem seguinte.

Se as estações inicial e final forem a 1 e a 4 e o monumento estiver na 7, então mudaria de comboio na estação 2: poderia deslocar-se pelas seguintes estações, por esta ordem: 1 -> 2 -> 3 -> 7 -> 3 -> 2 -> 4, demorando exatamente 6 horas para completar este percurso. Se as estações inicial e final forem a 1 e a 3, e o monumento na 6 já teria de mudar na estação 3, fazendo o caminho: 1 -> 2 -> 3 -> 6 -> 3.

Além do Francisco, muitos outros vão viajar e querem visitar diversos monumentos. Consegues ajudar o Francisco e os outros a escolher os seus percursos?

O Problema

Dado um conjunto de N estações e N - 1 ligações entre elas, e C perguntas do tipo: dadas duas estações iniciais A e B e um monumento M, calcular a estação do caminho de A para B que está mais próxima de M.

Input

Na primeira linha vem 1 inteiro N, que representa o número de estações

Seguem-se N - 1 linhas, cada uma com dois inteiros, representando uma ligação entre duas estações. Nota que as duas estações são sempre diferentes e não há nenhuma ligação repetida.

Segue-se uma linha com um inteiro C que representa o número de perguntas diferentes.

Seguem-se C linhas, cada uma com três inteiros que representam estações iniciais e finais para viagens e a localização do monumento, por esta ordem.

Output

O output contém um inteiro por cada uma das C viagens, que representa a estação pedida.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 5 grupos com restrições adicionais diferentes:

Input do Exemplo 1

7
1 2
2 3
2 4
3 6
3 7
4 5
2
1 4 7
1 3 6

Output do Exemplo 1

2
3

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

10
1 2
2 3
1 4
4 5
4 6
4 7
5 8
6 9
7 10
4
3 9 2
10 6 4
1 3 9
4 8 1

Output do Exemplo 2

2
4
1
4