XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: onibus.x, onde x deve ser c, cpp, java, js ou py

Ô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

A primeira linha da entrada contém três inteiros N, A e B, representando o número de cidades na Linearlândia, a cidade origem e a cidade destino, respectivamente. As N-1 linhas seguintes contém, cada uma, dois inteiros P e Q, indicando que existe uma linha de ônibus ligando diretamente as cidades P e Q.

Saída

Seu programa deve imprimir uma linha contendo um inteiro representando quantos ônibus é preciso pegar para ir de A até B.

Restrições

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

Exemplos

Entrada
4 2 4
1 2
2 3
3 4
Saída
2
	

 

Entrada
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
Saída
4
	

 

Tarefas Programação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação