34157번 - Split the SSHS 5 서브태스크

문제

서울과학고등학교에는 1ドル$번부터 $N$번까지 번호가 부여된 $N$개의 건물과 두 건물 사이를 연결하는 $N - 1$개의 길이 존재한다. 서울과학고등학교의 어떤 두 건물 사이도 몇 개의 길을 이용하여 이동할 수 있음이 보장된다. 즉, 서울과학고등학교는 트리이다.

어느 날 악당 경곽이는 서울과학고등학교의 각 건물에 함정을 설치했다. 경곽이는 $i$번 건물에 $A_i$개의 함정을 설치했으며, 어느 하나의 건물에 설치된 모든 함정은 서로 다른 건물과 연결되어 있다. $i$번 건물에 누군가가 들어오면, $A_i$개의 함정 중 무작위로 하나가 작동해 해당 함정과 연결된 건물 중 하나가 잠긴 상태가 되어 더 이상 출입할 수 없게 된다. 이때, $A_i$개의 함정이 작동할 확률은 모두 동일하며, 정확히 하나의 함정만 작동한다. 연결된 건물이 잠긴 상태여도 확률 변동 없이 함정이 작동할 수 있다.

1ドル$번 건물에서 수업을 마친 설곽이는 다음 수업을 위해 2ドル$번 건물부터 $N$번 건물 중 하나로 이동하려 한다. 이때, 설곽이는 효율적이므로 항상 최소한의 건물 간 이동을 행하는 경로(즉 최단경로)를 택하여 길을 통해 이동한다. 설곽이의 목적지가 2ドル$번 건물부터 $N$번 건물인 총 $N-1$가지 경우에 대하여 1ドル$번 건물을 떠나 원하는 건물에 도달할 수 있는 확률을 구해보자. 설곽이가 떠나기 전 모든 함정들은 초기화된다. 1ドル$번 건물의 함정은 설곽이가 출발하기 직전 작동한다.

입력

첫 번째 줄에 서울과학고등학교의 건물 개수를 나타내는 정수 $N$이 주어진다. (1ドル \leq N \leq 100 ,円 000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 경곽이가 설치한 함정에 대한 정보가 주어진다. 이 중 $i$번째 줄에는 경곽이가 $i$번 건물에 설치한 함정의 개수인 $A_i$가 주어지며 같은 줄에 각각의 함정이 연결된 $A_i$개의 건물 번호를 나타내는 정수 $a_{i1}, ,円 a_{i2}, ,円 \cdots, ,円 a_{iA_{i}}$가 공백으로 구분되어 주어진다.

(0ドル \leq A_i $이며, $A_i$의 합은 100ドル ,円 000$을 넘지 않는다. 각 $i$에 대해 $a_{i1}, ,円 a_{i2}, ,円 \cdots, ,円 a_{iA_{i}}$는 모두 다르며, $a_{ij} \neq i$이다.)

$N + 2$번째 줄부터 $N - 1$개의 줄에 걸쳐, 두 정수 $u,ドル $v$가 공백으로 구분되어 주어진다. 이는 $u$번 건물과 $v$번 건물을 연결하는 길이 존재함을 의미한다. (1ドル \leq u, v \leq N$)

입력으로 주어지는 서울과학고등학교의 구조는 올바른 트리임을 보장한다.

출력

1ドル$번 교실에서 각 학생이 2ドル$번 교실부터 $N$번 교실까지 도달할 수 있는 확률을 998ドル ,円 244 ,円 353$으로 나눈 나머지를 순서대로 N-1줄에 거쳐 한 줄에 하나씩 출력하라. 998ドル ,円 244 ,円 353$은 소수이다. 각 교실에 도달할 확률이 유리수임을 증명할 수 있다.

기약 분수 $\displaystyle \frac{p}{q}$ ($p \geq 0, q > 0, \gcd(p, q) = 1$)에 대해 소수 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod {M}$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다.

제한

서브태스크

노트