São João
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 saída 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
| Entrada | Saída |
| 7
1 2 1 5 2 3 2 4 5 6 6 7 7 1 1 1 2 1 3 1 4 4 4 4 5 4 1000000 |
2
3 4 4 5 6 7 |