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 |