감염

한 비밀 조직에서 긴급 상황이 발생했다. 근무 중간에 직원 한 명이 매우 위험한 colonavirus 감염 증상으로 입원했다. 관리진은 아직 증상이 나타나지 않은 직원들 중 누가 여전히 감염될 수 있는지 알고 싶어 한다.

조직에는 $n$명의 직원이 있으며, 1부터 $n$까지 정수로 번호가 매겨져 있다. CCTV 녹화 영상을 통해 관리진은 직원들이 언제 서로 접촉했는지 파악했다. 관리진은 다음 가정도 고려했다.

• 근무일 시작 시점에 정확히 한 명만 감염되어 있으며, 각 초기 상태가 나올 확률은 $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$가 주어진다 ($1 \le x_i, y_i \le n$, $x_i \ne y_i$).

모든 접촉은 시간 순서대로 주어진다.

$n$개의 줄을 출력한다. $i$번째 줄에는 직원 $i$가 감염될 확률을 기약분수 $a/b$ 형태로 출력한다.