Problema C - Problemas no parque

O pequeno Henrique foi visitar o novo Parque de dinossauros no Porto com a sua família enquanto o seu irmão participava nas ONI. Após muito passear já tinha visto quase tudo, até que encontrou o assustador Tiranossauro. Ficou tão assustado que quis fugir para o sítio de interesse do parque mais afastado possível. No entanto o mapa parecia muito complexo para ele descobrir para onde ir.

O mapa está organizado em pontos de interesse, por onde o Henrique pode passar, e ligações (pequenas estradas) de comprimento igual. Após analisar com muito cuidado, chegou à conclusão que entre quaisquer dois pontos de interesse existe no mínimo um e no máximo dois caminhos simples. Isto é, para ir de um ponto para o outro, no máximo, existem dois caminhos que diferem em pelo menos um ponto e não repetem pontos, e no mínimo um nas mesmas condições. Ainda mais, entre dois pontos existe no máximo uma estrada (uma ligação direta).

Além disso, o parque tem vários dinossauros que assustam o Henrique e por isso para cada um precisa de saber para onde deve fugir. Ou seja, para cada ponto com um dinossauro assustador o Henrique quer saber quanto tem de andar para chegar ao ponto de interesse mais afastado desse ponto, ou seja, qual a distância entre o ponto atual e o ponto mais afastado desse ponto atual. A distância entre dois pontos de interesse é dada pelo menor número de ligações para ir de um ponto ou outro. Nota também que os dinossauros estão todos em pontos de interesse.

Considera por exemplo o seguinte mapa:

Exemplo

Há dois pontos de interesse com dinossauros. O ponto 4, do qual os pontos mais distantes são o 1 e 2, e logo a resposta é 3, a distância a que estes dois se encontram. De seguida, o ponto 0, do qual o ponto mais distante é o 4, logo a resposta para este caso seria 2.

Sabendo isto, e dado o mapa, será que consegues ajudar o pequeno Henrique a esconder-se e dizer-lhe a que distância está o ponto mais afastado de cada ponto onde ele se possa assustar? Nota que o Henrique quer chegar ao ponto o mais rápido possível, por isso a distância é percorrendo o menor caminho que existe.

O Problema

Dado o número N de pontos de interesse numerados de 0 a N - 1, o número L de ligações entre eles por onde o Henrique pode passar, responder a Q perguntas de qual a distância do ponto mais afastado do ponto Qi.

Input

Na primeira linha vêm três inteiros, o primeiro representando o número N de pontos de interesse, o segundo o número L de ligações e o terceiro o número Q de perguntas.

Seguem-se L linhas, onde a i-ésima tem um par Ai Bi, que representam uma ligação bidirecional entre Ai e Bi.

Finalmente, vêm Q linhas, cada uma com um inteiro Qi indicando o ponto de interesse da i-ésima pergunta (um número entre 0 e N-1).

Output

O output deve conter Q linhas com a reposta a cada uma das perguntas.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

N ≤ 100 000       Número de pontos
L ≤ 500 000       Número de ligações
Q ≤ 100 000       Número de perguntas

Os casos de teste deste problema estão organizados em 5 grupos com restrições adicionais diferentes:

Grupo Número de Pontos Restrições adicionais
1 20 N ≤ 1000, L ≤ 5000 e Q ≤ 1000
2 25 Há exatamente um caminho entre cada ponto
3 5 Há exatamente dois caminhos entre cada ponto
4 20 Há um conjunto de três pontos ligados dois a dois
5 30 -

Input do Exemplo 1

5 4 2
4 3
3 0
0 2
1 0
4
0

Output do Exemplo 1

3
2

Input do Exemplo 2

8 8 5
7 6
4 2
3 1
4 5
2 3
0 6
7 2
3 7
3
7
4
5
4

Output do Exemplo 2

3
3
4
5
4

Prova de Seleção para as IOI'2018
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
(10 de Junho de 2018)