암살자

암살자들의 세계에서는 경쟁이 치열하고, 모두가 우위를 차지하기 위해 싸운다. 경쟁자를 제거하기 위해 많은 암살자가 다른 암살자를 암살하기까지 한다. 암살자 여러 명이 서로를 죽이려 할 때, 누가 살아남고 누가 죽는지 알아내야 한다.

암살자들은 일반적으로 실행 전에 치밀한 계획을 세우며, 같은 목표를 제거하기 위한 여러 번의 시도를 계획한다. 첫 번째 시도가 실패할 경우를 대비한 두 번째 시도, 그다음 백업을 위한 세 번째 시도 등이 있다. 뛰어난 분석 능력으로 암살자들은 주어진 암살 시도가 성공할 확률을 매우 정확하게 판단할 수 있다.

한 무리의 암살자에 대해 계획된 암살 시도 목록이 주어졌을 때, 모든 시도가 끝난 뒤 각 암살자가 살아 있을 확률은 얼마인가? 암살 시도를 수행하려면 암살자가 아직 살아 있어야 하므로, 이미 암살되어 죽은 암살자의 시도는 취소된다.

첫 번째 줄에는 두 정수 n과 m이 주어진다. n(1 ≤ n ≤ 15)은 암살자의 수이고, m(0 ≤ m ≤ 1000)은 계획된 암살 시도의 수이다. 암살자는 1번부터 n번까지 번호가 매겨진다.

다음 m개의 줄에는 각각 두 정수 i, j와 실수 p가 주어지며, 암살자 i가 암살자 j를 암살하려 한다는 것(1 ≤ i, j ≤ n, j ≠ i)과 이 시도가 확률 p로 성공한다는 것(0 ≤ p ≤ 1, 소수점 이하 최대 6자리)을 나타낸다. 계획된 시도는 시간 순서대로 처음부터 마지막까지 나열되며, 두 시도가 동시에 일어나지 않는다.

n개의 줄을 출력하며, i번째 줄에는 m번의 암살 시도가 모두 끝난 뒤 암살자 i가 살아 있을 확률을 출력한다. n명의 암살자 중 누구도 이 m번의 시도에서 암살당하는 것 외의 다른 원인으로 죽지 않는다고 가정할 수 있다. 확률은 절대 오차 10−6 이하로 정확해야 한다.