Vida de inseto

Em certa árvore de uma floresta distante, existe uma comunidade de lagartas que adoram saltar de uma folha para outra. Existe apenas um caminho entre uma folha e outra na árvore, e o salto só pode ocorrer entre folhas conectadas por um mesmo galho. Duas dessas lagartas são muito amigas, e sempre que se encontram em uma mesma folha, param para conversar sobre a vida. Porém, se elas se encontram em folhas vizinhas, elas seguem seu caminho infinitamente. Elas sempre seguem o caminho que vai em direção à folha inicial da outra lagarta. Seu desafio é, dada as posições das duas lagartas, dizer onde elas irão se encontrar.

Entrada

A entrada começa com um inteiro $N$ $(1 < N < 5000)$ o número de folhas existentes na árvore. Nós assumimos que as folhas são numeradas de $1$ até $N$. Cada uma das $N-1$ linhas seguintes descrevem os galhos da árvore; cada galho é descrito por dois inteiros $a$ e $b$, o que significa que esse galho liga as folhas $a$ e $b$. Na linha seguinte, segue um inteiro $k$ $(1 < k < 500)$, representando a quantidade de posições das lagartas na árvore que você terá que considerar. Cada uma das $k$ linhas seguintes contém dois inteiros positivos (não maiores que $N$). Esse números definem as posições iniciais das formigas.

Saída

Seu programa deve imprimir $k$ linhas. A i-ésima linha deve conter uma das seguintes frases:

• As lagartas se encontram em $t$. Onde $t$ identifica a folha em que as lagartas se encontraram, ou
• As lagartas pularam para sempre a partir de $t$ e $r$. Sendo $t$ e $r$ as folhas vizinhas em que elas se encontram, onde $t \leq r$.

Exemplo

 

ENTRADA	SAÍDA
8 1 2 1 3 2 4 2 5 3 6 3 7 5 8 5 5 1 7 4 1 8 4 7 7 8	As lagartas se encontram em 2. As lagartas se encontram em 1. As lagartas pularam para sempre a partir de 2 e 5. As lagartas se encontram em 1. As lagartas pularam para sempre a partir de 1 e 2.