Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SAOJOAO - 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 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

Entrada

Saída

7

 

2

1

2

3

1

5

4

2

3

4

2

4

5

5

6

6

6

7

7

7

 

 

11

12

13

14

4 4

4 5

4 1000000


Adicionado por:Mateus Dantas [ UFCG ]
Data:2013-12-10
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Olimpiada Brasileira de Informatica 2013 - Seletiva para IOI 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.