Museum

题意翻译

Petya和Vasya去参观一座城堡。城堡有n个房间，m条走廊，使n个房间互相联通。 Petya与Vasya决定分开去看各自想看的内容，并约定于下午六点在一个房间集合。然而他们并没有确认是在哪个房间集合——当时间到了，他们就会开始到处乱跑，试图找到对方（他们是远古人类并不会用电话）。 然而，即使不管整个寻找的过程，他们仍无法满足对艺术的欣赏欲望——因此（？？？）他们都遵循以下寻找的策略：每分钟决定去哪个房间——各有一个概率p[i],代表他这一分钟除了哪都不去（也就是原地不动）。他有 1-p[i] 的概率随机去到一个相邻的房间（每个选择为等概率事件）。以上部分中,i 代表现在的房间序号。远古时期，建筑需要大量氪金，因此任意一条走廊只连接两个房间，任意两个房间之间最多有一条走廊直接将它们连通。 Petya与Vasya都很着急。因为走廊很黑，他们不可能在那里会面。不过，走廊可以从任意方向被通过（因此，Petya与Vasya有可能同时焦急地穿过同一条走廊却找不到对方）。在他们会面之前，Petya与Vasya都不会停下脚步。更准确的说，二者仅在同时到达同一个房间时才算相遇。 假设下午六点钟他们分别位于房间a和房间b。对于每个房间，请你计算出Petya与Vasya在那里相遇的概率。 输入 第一行有四个整数：房间总数n(1<=n<=22),走廊总数m(n-1<=m<=n(n-1)/2),Petya与Vasya的初始位置a,b。 接下来m行每行有一对数字——表示这两个房间之间有一条走廊。 再接下来n行，每行有一个四位小数——停在对应的房间的概率pi。 保证整个城堡连通。 输出 仅一行，以空格分开n个答案——在每个房间相遇的概率。 感谢@GodelnShit 提供的翻译

题目描述

One day as Petya and his friend Vasya were having one of their numerous trips, they decided to visit a museum castle. The museum has a specific shape: it consists of $ n $ rooms connected with $ m $ corridors so that one can access any room from any other one. After the two friends had a little walk around the museum, they decided to split and watch the pieces of art each of them found interesting. They agreed to meet in one of the rooms at six p.m. However, they forgot one quite essential thing: they didn't specify the place to meet and when the time came, they started to rush about the museum looking for each other (they couldn't call each other as roaming made a call's cost skyrocket). Yet, even despite the whole rush, they couldn't get enough of the pieces of art, that's why each of them has the following strategy: each minute he make a decision where to go — with probability $ p_{i} $ he doesn't move to any other place during this minute (i.e. he stays in the room). With probability $ 1-p_{i} $ he equiprobably choose one of the adjacent rooms and went there along the corridor. Here $ i $ is the ordinal number of the current room. Building was expensive in ancient times, that's why each corridor connected two different rooms, and any two rooms had no more than one corridor between them. The boys act simultaneously. As the corridors are dark, it is impossible to meet there; however, one can walk along the corridors in both directions (besides, the two boys can be going through the same corridor simultaneously without meeting). The boys act like that until they meet each other. More formally, the two friends meet when at some moment of time both of them decided to appear in the same room. For each room find the probability that the boys will meet there considering that at 6 p.m. they are positioned in rooms $ a $ and $ b $ correspondingly.

输入输出格式

输入格式

The first line contains four integers: $ n $ $ (1<=n<=22) $ , representing the numbers of rooms; $ m $ , representing the number of corridors; $ a,b $ $ (1<=a,b<=n) $ , representing the numbers of Petya's and Vasya's starting rooms correspondingly. Next $ m $ lines contain pairs of numbers — the numbers of rooms connected by a corridor. Next $ n $ lines contain probabilities $ p_{i} $ $ (0.01<=p_{i}<=0.99) $ with the accuracy of up to four digits after the decimal point — the probability to stay in room $ i $ . It is guaranteed that every room can be reached from every other room by corridors.

输出格式

In the only line print $ n $ space-separated numbers, the $ i $ -th number should represent the probability that the friends meet in the $ i $ -th room with absolute or relative error of no more than $ 10^{-6} $ .

输入输出样例

输入样例 #1

2 1 1 2
1 2
0.5
0.5

输出样例 #1

0.5000000000 0.5000000000 

输入样例 #2

4 4 1 2
1 2
2 3
3 4
4 1
0.5
0.5
0.5
0.5

输出样例 #2

0.3333333333 0.3333333333 0.1666666667 0.1666666667 

说明

In the first sample the museum is symmetric. That means the probabilities to meet in rooms 1 and 2 are equal. And their sum equals to one. So, each probability equals $ 0.5 $ .