题目描述

一天，Petya 和他的朋友 Vasya 在他们众多旅行中的一次旅途中，决定参观一座城堡博物馆。博物馆的形状很特别：它由 $n$ 个房间和 $m$ 条走廊组成，使得从任意一个房间都可以到达任意另一个房间。

两位朋友在博物馆里稍微逛了一会儿后，决定分开去看各自感兴趣的艺术品。他们约定在下午六点于某个房间见面。然而，他们忘了一件相当重要的事：他们没有指定见面的地点。到时间后，他们开始在博物馆里四处奔走寻找对方（他们不能打电话，因为漫游费用会让通话成本飙升）。

不过，即使如此匆忙，他们仍然看不够这些艺术品，因此每个人都采用如下策略：每分钟他都会决定去哪里——以概率 $p_{i}$ ，他在这一分钟内不会移动到别的地方（即留在原房间）。以概率 $1-p_{i}$ ，他会等概率地选择一个相邻房间，并沿走廊走过去。这里 $i$ 是当前房间的编号。古代建造建筑十分昂贵，因此每条走廊都连接两个不同的房间，并且任意两个房间之间至多只有一条走廊。

两人同时行动。由于走廊很暗，他们不可能在走廊里相遇；不过，走廊可以双向通行（此外，两人可以同时经过同一条走廊而不会相遇）。两人会一直这样行动，直到他们相遇。更形式化地说，当在某一时刻两位朋友都决定出现在同一个房间时，他们就相遇了。

对于每个房间，求两人会在该房间相遇的概率，已知下午六点时他们分别位于房间 $a$ 和 $b$ 。

输入格式

第一行包含四个整数：$n$ $(1\le n\le 22)$ ，表示房间数量；$m$ $(n-1\le m\le \frac{n(n-1)}{2})$，表示走廊数量；$a,b$ $(1\le a,b\le n)$ ，分别表示 Petya 和 Vasya 的起始房间编号。

接下来 $m$ 行每行包含一对数字——表示由一条走廊连接的两个房间编号。接下来 $n$ 行包含概率 $p_{i}$ $(0.01\le p_{i}\le 0.99)$ ，精确到小数点后最多四位——表示留在房间 $i$ 的概率。

保证任意房间都可以通过走廊到达任意其他房间。

输出格式

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

2 1 1 2
1 2
0.5
0.5

0.5000000000 0.5000000000

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

0.3333333333 0.3333333333 0.1666666667 0.1666666667

提示

在第一个样例中，博物馆是对称的。这意味着在房间 1 和房间 2 相遇的概率相等。并且它们的和等于一。因此，每个概率都等于 $0.5$ 。