Ônibus

A Linearlândia é composta de N cidades, numeradas de 1 até N. Para alguns pares de cidades existe uma linha de ônibus que faz o trajeto de ida e volta diretamente entre as duas cidades do par. Os pares de cidades ligados diretamente por uma linha de ônibus são escolhidos de forma que sempre é possível ir de qualquer cidade para qualquer outra cidade por um, e somente um, caminho (um caminho é uma sequência de linhas de ônibus, sem repetição).

Dada a lista de pares de cidades ligados diretamente por linhas de ônibus, uma cidade origem e uma cidade destino, seu programa deve computar quantos ônibus é preciso pegar para ir da origem ao destino. Por exemplo, na figura, para ir da cidade 2 para a cidade 12 é preciso pegar 4 ônibus.

Entrada

Saída

Restrições

• 2 ≤ N ≤ 10000
• 1 ≤ A ≤ N, 1 ≤ B ≤ N, A ≠ B
• 1 ≤ P ≤ N, 1 ≤ Q ≤ N

Exemplos

4 2 4
1 2
2 3
3 4

2
	

16 2 12
3 5
12 3
5 1
2 1
4 1
6 1
7 1
12 8
12 9
12 10
12 11
3 13
13 14
15 13
15 16

4