Infection

An emergency happened in one secret organization. In the middle of the working day, one of the employees was hospitalized with symptoms of an extremely dangerous colonavirus infection. Management now wants to know which employees can still be infected, even though their symptoms have not yet appeared.

The organization has $n$ employees, numbered with integers from 1 to $n$. From CCTV recordings, management established when each pair of employees contacted each other. Management also made the following assumptions.

• At the beginning of the working day, exactly one employee was infected, and each initial state has probability $1/n$.
• If two employees come into contact, and one is infected and the other is not, the healthy employee becomes infected with probability $1/2$. If both are healthy, or both are infected, nothing happens.
• An infected employee cannot recover. He remains infected until the end.
• It is known that employee $k$ was eventually infected.

The contacts are given in chronological order. Determine the probability that each employee is infected under the assumptions above.

The first line contains three integers $n$, $k$ and $m$, the number of employees, the number of the infected employee, and the number of contacts ($2 \le n \le 15$, $1 \le k \le n$, $1 \le m \le 50$).

Each of the following $m$ lines contains two integers $x_i$ and $y_i$, the indexes of the employees who took part in the $i$-th contact ($1 \le x_i, y_i \le n$, $x_i \ne y_i$).

All contacts are given in chronological order.

Print $n$ lines. On the $i$-th line, print the probability that employee $i$ is infected as an irreducible fraction $a/b$.