Informática Intermediário - Semana 65

Olimpíada

Bedro e Bismarx estão organizando a Olimpíada Fortalezense de Astronomia (UFA, era para ser OFA mas eles são muito zoeiros e não iam perder o trocadilho). E após muitas conversas e debates eles decidiram que as questões e a produção da prova iria ser feita em uma sala e a realização da mesma em outra. A sede da UFA é um prédio que possui $N$ salas e $N - 1$ corredores conectando-as e pode-se ir de qualquer sala $A$ para qualquer outra sala $B$ utilizando apenas os corredores do prédio. A olimpíada está chegando e eles precisam decidir quais serão as salas utilizadas para a produção e aplicação da prova. Como o prédio possui muitas salas e eles não podem escolher duas salas próximas demais para evitar algum tipo de vazamento das questões no dia da prova e nem duas salas distantes demais pois dificulta o transporte das mesmas. Eles definiram que a distância entre duas salas $A$ e $B$ é igual a quantidade de salas que existem no caminho de $A$ para $B$ (ou de $B$ para $A$). Sabendo que você é um excelente programador e um grande amigo de Bedro e Bismarx, eles pediram sua ajuda para resolver esse problema. Então, dada um lista de $Q$ perguntas do tipo $A$ $B$, responda, para cada pergunta, a distância entre as salas $A$ e $B$.

Entrada

A primeira linha da entrada contém um inteiro $N$ representando o número de salas na sede da UFA. As próximas $N - 1$ contém cada uma dois inteiros $u$ $v$, representando um corredor ligando as salas $u$ e $v$. A próxima linha contém um inteiro $Q$ representando a quantidade de perguntas feita por Bedro e Bismarx. E por fim as $Q$ linhas seguintes contém cada uma dois inteiros $A$ $B$, representando uma pergunta que foi descrita no enunciado acima.

Saída

Dada a i-ésima pergunta responda, a distância entre as salas $A_i$ e $B_i$.

Exemplos

Entrada	Saída
4 1 2 1 3 2 4 1 2 3	1