Informática Intermediário - Semana 75

Por incrível que pareça, Papai Noel ainda não começou a fabricar os presentes que serão entregues no natal. Para ele não se atrasar foi bolado um plano para agilizar as entregas e a fabricação.

O plano de Noel consiste em escolher duas crianças ($A$ e $B$), para serem as primeiras a receberem os presentes, mas o que ele reparou é que no caminho entre a casa da criança $A$ até a casa da criança $B$, ele acabará passando por outras crianças que também enviaram suas cartinhas com o que gostariam de ganhar. Portanto Noel decidiu que irá entregar todos os presentes das crianças que estão entre as casas $A$ e $B$ em apenas uma viagem.

A parte da entrega é muito simples para o Noel, mas ele precisa otimizar a compra de matérias-primas para a confecção de todos os presentes, e é aqui que você entra para o auxiliar.

Será dado a você o mapa com todas as casas onde ocorrerá entregas, que consiste em $N$ casas, com $N$ - 1 ligações, tendo exatamente um caminho entre cada uma delas, como Noel sempre viaja de trenó, todas as ligações podem ser usadas nos dois sentidos. Após isto Noel irá fazer diversas perguntas do tipo $A$ $B$, e você deverá responder quantos presentes distintos ele terá que entregar no caminho entre a casa $A$ e a casa $B$.

Entrada