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