IF672 - Algoritmos e Estruturas de Dados
novembro 2002 a março 2003

2 - As Aventuras de Jamilson: Museu

 
 
     Jamilson, um garoto acompanhado de seus pais, está no museu de paleontologia mais famoso da França.
Não só ele, como a maioria dos garotos, querem chegar rapidamente na atração principal: o Tiranossauro Rex. O problema é que seus pais não permitem que ele saia de perto deles. Jamilson gostaria de saber o quão mais rápido seria para chegar na atração principal em comparação com os pais deles, se os mesmos seguissem os conselhos de Jamilson.
    Os pais de Jamilson percorrem o museu sem nenhuma lógica precisa. Apenas garantem que nunca visitarão o mesmo local duas vezes se não for estritamente necessário, e visitarão todo o museu. Eles seguem sempre o primeiro salão ainda não visitado a partir do salão que está agora (busca em profundidade).
    Jamilson procura chegar o mais rápido possível na atração principal (busca em largura).
    Considere que os corredores entre os salões têm o mesmo tamanho. E cada visita a um salão demora 1 hora.
    O problema é achar a diferença entre o tempo que demoraria se Jamilson andasse sozinho em relação ao tempo que demora com os pais.



Entrada e Saída de dados

A entrada consiste em várias conjuntos de dados.
Cada conjunto começa com quatro valores:
    (N < 100) indicando a quantidade de salões no museu
    (E < 1000) indicando a quantidade de corredores no museu
    (s <= N) indicando a entrada do museu (considere como um salão)
    (t <= N) indicando o salão da atração principal.
Segue E linhas cada uma com dois valores (s1, s2), indicando que existe um corredor de s1 a s2 (0 < s1,s2 <= N).
Fim de arquivo indica o final da entrada.
A saída consiste do valor inteiro (quantidade de horas) indicado na especificação do problema (a diferença entre [quantidade de salões visitados pela família com os pais guiando] e [quantidade de salões que seriam visitados se Jamilson tivesse guiando a família]).

NOTA: Se houver mais de uma opção, tanto o casal como Jamilson prefere os salões com números menores.


Entrada exemplo

 
10 9 1 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

10 9 1 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

10 17 1 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

Saída correspondente 

0
8
8