某秘密组织发生了一起紧急事件。在工作日的中途，一名员工因感染了一种极其危险的 colonavirus 而住院。因此，组织管理层希望确定哪些员工可能已经被感染，尽管他们尚未表现出疾病症状。

该组织共有 $n$ 名员工，编号为 $1$ 到 $n$。通过监控录像，管理层确定了员工之间接触的时间。此外，管理层还考虑了以下假设：

• 在工作日开始时，恰好有一名员工被感染，且每种初始感染状态发生的概率均为 $1/n$。
• 如果两名员工发生接触，其中一人已感染而另一人未感染，则健康的员工有 $1/2$ 的概率被感染。如果两名员工均健康或均已感染，则不会发生任何变化。
• 如果一名员工被感染，他不会突然康复，即他会保持感染状态直到最后。
• 已知编号为 $k$ 的员工最终被感染。

给定一份按时间顺序排列的员工接触列表。请根据上述假设，确定每名员工被感染的概率。

输入格式

第一行包含三个整数 $n$、$k$ 和 $m$，分别表示员工总数、最终被感染的员工编号以及接触次数（$2 \le n \le 15$，$1 \le k \le n$，$1 \le m \le 50$）。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示参与第 $i$ 次接触的员工编号（$1 \le x_i, y_i \le n$，$x_i \neq y_i$）。

列表中的所有接触均按时间顺序给出。

输出格式

输出 $n$ 行。第 $i$ 行输出第 $i$ 名员工被感染的概率，以最简分数 $a/b$ 的形式表示。具体格式请参考样例。

样例

输入 1

3 2 1
1 2

输出 1

2/3
1/1
0/1

输入 2

3 2 2
1 2
2 3

输出 2

1/2
1/1
5/8

输入 3

4 1 4
1 2
2 3
3 4
4 1

输出 3

1/1
19/37
17/37
27/37