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.

Problem hidden

SAOJOAO - São João

no tags 

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


Added by:Mateus Dantas [ UFCG ]
Date:2013-12-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Olimpiada Brasileira de Informatica 2013 - Seletiva para IOI 2014