CF113D Museum

有一天，Petya 和他的朋友 Vasya 在一次旅行中，决定参观一座博物馆城堡。这个博物馆有一个特殊的结构：它由 $n$ 个房间和 $m$ 条走廊组成，任意两个房间之间都可以通过走廊互相到达。 两位朋友在博物馆里逛了一会儿后，决定分开各自欣赏感兴趣的艺术品。他们约定在下午六点在某个房间见面。然而，他们忘记了一个很重要的事情：没有指定具体的见面地点。等到时间到了，他们开始在博物馆里四处寻找对方（由于漫游费用太高，他们无法打电话联系）。 即便如此，他们依然沉迷于艺术品，因此每个人都有如下的行动策略：每分钟，他会做出决定——以概率 $p_i$，他会留在当前房间不动；以概率 $1-p_i$，他会等概率地选择一个相邻的房间，并通过走廊前往那里。这里 $i$ 表示当前所在房间的编号。由于古代建筑成本高昂，每条走廊只连接两个不同的房间，且任意两房间之间最多只有一条走廊。 两个人是同时行动的。由于走廊很黑，他们无法在走廊里相遇；不过，走廊是双向通行的，并且两个人可以同时走在同一条走廊上而不会遇见。两人会一直这样行动，直到他们在同一个房间相遇。更正式地说，当某一时刻两人都出现在同一个房间时，他们就算相遇了。 对于每个房间，求出两人最终在该房间相遇的概率。已知六点时，Petya 和 Vasya 分别在房间 $a$ 和 $b$。

第一行包含四个整数：$n$（$1 \leq n \leq 22$），表示房间数；$m$，表示走廊数；$a, b$（$1 \leq a, b \leq n$），表示 Petya 和 Vasya 的起始房间编号。 接下来的 $m$ 行，每行包含两个整数，表示一条走廊连接的两个房间编号。 接下来的 $n$ 行，每行包含一个概率 $p_i$（$0.01 \leq p_i \leq 0.99$，精确到小数点后四位），表示留在第 $i$ 个房间的概率。 保证任意两个房间之间都可以通过走廊互相到达。

一行输出 $n$ 个用空格分隔的数，第 $i$ 个数表示两人在第 $i$ 个房间相遇的概率，绝对误差或相对误差不超过 $10^{-6}$。

在第一个样例中，博物馆是对称的，因此在房间 1 和房间 2 相遇的概率相等，并且它们的和为 1。所以每个概率都是 $0.5$。 由 ChatGPT 4.1 翻译