13640번 - Perdido na Noite 다국어

Numa cidade da Nlogônia, o sistema viário é composto de N rotatórias e N − 1 ruas, sendo que cada rua liga duas rotatórias distintas. Utilizando o sistema viário, é possível ir de qualquer rotatória para qualquer outra rotatória da cidade.

A cidade possui apenas dois hotéis: um barato, localizado na rotatória B, e um caro, localizado na rotatória C. Um turista veio à cidade para celebrar o aniversário de um amigo, cuja festa está sendo realizada em um clube localizado na rotatória A. Como o turista não fez reserva em nenhum dos hotéis e a noite está agradável, após a festa ele decidiu passear a pé pelas ruas e rotatórias até encontrar um dos hotéis (ele também decidiu hospedar-se no primeiro hotel que encontrar).

Seu plano foi dificultado porque como ele não conhece a cidade e bebeu um pouco além da conta, todas as ruas lhe parecem iguais. Assim, ele decidiu usar a seguinte estratégia: a cada rotatória ele escolhe, com probabilidade uniforme, uma das ruas que saem da rotatória, e usa essa rua para ir a uma outra rotatória, até chegar à rotatória onde um dos hotéis está localizado. Note que como o turista não consegue distinguir as ruas, pode ocorrer de ele escolher a mesma rua pela qual chegou à rotatória.

Você deve escrever um programa que, dadas a descrição do sistema viário, a localização A da festa de aniversário, a localização B do hotel barato e a localização C do hotel caro, determine a probabilidade de o turista chegar ao hotel barato antes de chegar ao hotel caro.

A primeira linha de um caso de teste contém quatro inteiros N, A, B e C, indicando respectivamente o número de rotatórias do sistema viário, a rotatória onde a festa de aniversário foi realizada, a rotatória onde o hotel barato está localizado, e a rotatória onde o hotel caro está localizado. Cada uma das N − 1 linhas seguintes contém dois inteiros X e Y , indicando que existe uma rua que liga as rotatórias X e Y .

Restrições

• 3 ≤ N ≤ 100
• B ≠ C, A ≠ B, A ≠ C.
• 1 ≤ A, B, C ≤ N
• 1 ≤ X, Y ≤ N.
• X ≠ Y .

Seu programa deve imprimir uma única linha, contendo a probabilidade de o turista chegar ao hotel barato antes de chegar ao hotel caro, com 6 casas decimais.