URI Online Judge | 1227

Midnight Cowboy

Maratona de Programação da SBC Brazil

Timelimit: 2

In a city of Nlogonia, the road system is composed of N traffic circles and N−1 streets, each street connecting two distinct traffic circles. Using the road system, one can go from any traffic circle to any other traffic circle in the city.

The city has only two hotels: an inexpensive hotel, located at the traffic circle B, and an expensive hotel located at traffic circle C. A tourist came to town to celebrate the birthday of a friend, whose party is being held at a club in the traffic circle A. As the tourist did not make a reservation for any of the hotels and since the night is pleasant, after the party is over he decides to walk along the streets and traffic circles to find one of the hotels (he also decides to stay at the first hotel he finds).

His plan is more difficult than he expected, because he is not familiar with the city and also because he drank a little bit too much. All the streets look the same to him. Thus he decides to use the following strategy: at each traffic circle, he chooses, with uniform probability, one of the streets leaving the traffic circle, and uses that street to go to another traffic circle, until he reaches the traffic circle where a hotel is located. Note that as the tourist cannot distinguish the streets, it is possible for him to choose the same street more than once.

You should write a program that, given the description of the city road system, the location A of the birthday party, the location B of the inexpensive hotel and the location C of the expensive hotel, determines the probability that he will get to the inexpensive hotel before reaching the expensive hotel.


The input contains several test cases. The first line of a test case contains four integers N (3 ≤ N ≤ 100), A (1 ≤ A), B and C (CN), indicating the number of traffic circles, the traffic circle where the birthday party is held, the traffic circle where the inexpensive hotel is located, and the traffic circle where the expensive hotel is located. Each of the N−1following lines contains two integers X (1 ≤ X) e Y (YN), indicating that there is a street connecting the traffic circles X and Y.

Note: B != C, A != B, A != C e X != Y


Your program must print a single line containing the probability, with 6 decimal places, that the tourist will arrive at the inexpensive hotel before arriving at the expensive hotel.

Sample Input Sample Output

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