SPOJ Brasil

O Maior São João do Mundo é um evento que ocorre anualmente na cidade de Campina Grande, no estado da Paraíba (Brasil) durante todo o mês de junho. Milhares de pessoas se reúnem no conhecido Parque do Povo para comemorar o São João através de danças, espetáculos e brincadeiras.

Uma brincadeira não muito conhecida pelos participantes é a corrida do labirinto. Um labirinto é composto de N salas e N – 1 corredores que ligam as salas. Também se sabe que entre cada par de salas existe exatamente um caminho que as liga. No começo da brincadeira, o organizador escolhe uma sala A e grita para todos os participantes um inteiro M que representa a quantidade máxima de corredores que cada participante pode passar. Após isso, todos eles se dirigem a sala A e começam a brincadeira visitando as outras salas. O participante que visitar a maior quantidade de salas diferentes sem exceder o limite M de corredores é declarado o vencedor da brincadeira e ganha um milhão ( uma espiga de milho de aproximadamente 1 metro de altura ) como prêmio.

Joãozinho sendo um rapaz bastante inteligente, decidiu pedir sua ajuda, e por isso ele vai fornecer a você o mapa do labirinto e em cada brincadeira ele vai informar a sala A de inicio e o limite M de corredores. Para cada brincadeira, você deverá responder a Joãozinho qual a maior quantidade de salas diferentes que ele pode visitar, sabendo que ele pode passar por um mesmo corredor mais de uma vez.

Entrada

A primeira linha da entrada é composta de um inteiro N indicando a quantidade de salas do labirinto. As N – 1 linhas seguidas contém cada dois inteiros P e Q, indicando que existe um corredor entre as salas P e Q. A próxima linha da entrada contém um inteiro V indicando a quantidade de brincadeiras que vão ocorrer. As V linhas que seguem contém cada dois inteiros A e M, indicando a sala inicial e o limite M da quantidade de corredores que Joãozinho pode percorrer.

Saída

A saida deve conter V linhas contendo cada um inteiro X que representa a maior quantidade de salas que Joãozinho pode percorrer saindo da sala inicial de cada brincadeira e não ultrapassando o limite de corredores.

Restrições

1 ≤ N ≤ 105

1 ≤  P, Q ≤ N

1 ≤ V ≤ 106

1 ≤ A ≤ N

1 ≤ M ≤ 106

Exemplos

11

12

13

14

4 4

4 5

4 1000000