题目描述

一座城市的排水系统由 $n$ 个排水结点（编号 $1 \sim n$）和若干单向管道构成。每个结点有若干管道用于汇集来自其他结点的污水（汇集管道），也有若干管道向其他结点排出污水（排出管道）。

排水系统中有 $m$ 个污水接收口，编号为 $1, 2, \ldots, m$，污水只能从这些接收口流入系统，且这些结点没有汇集管道。系统中还有若干最终排水口，它们将污水送往处理厂——没有排出管道的结点即为最终排水口。

现在各接收口分别接收了 $1$ 吨污水。污水进入每个结点后，会均等地从该结点的每一条排出管道流向目标结点；最终排水口将污水排出系统。

请计算每个最终排水口排出的污水体积。系统设计保证管道不会形成回路。

输入格式

第一行两个以空格分隔的整数 $n, m$，分别表示排水结点数与接收口数量。

接下来 $n$ 行，第 $i$ 行描述结点 $i$ 的排出管道。每行第一个整数 $d_i$ 表示排出管道数量，随后 $d_i$ 个整数 $a_1, a_2, \ldots, a_{d_i}$ 为目标结点编号。

保证不会出现两条起始结点与目标结点均相同的管道。

输出格式

按编号从小到大的顺序，输出每个最终排水口排出的污水体积。每行输出两个以空格分隔的整数 $p$ $q$，表示体积为 $\frac{p}{q}$。要求 $p$ 与 $q$ 互素，$q = 1$ 时也需输出 $q$。

样例

5 1
3 2 3 5
2 4 5
2 5 4
0
0

1 3
2 3

提示

样例 1 解释

$1$ 号结点是接收口，$4, 5$ 号结点没有排出管道，为最终排水口。

$1$ 吨污水流入 $1$ 号结点后，均等流向 $2, 3, 5$ 号结点，各流入 $\frac{1}{3}$ 吨。

$2$ 号结点的 $\frac{1}{3}$ 吨均等流向 $4, 5$ 号结点，各流入 $\frac{1}{6}$ 吨。

$3$ 号结点的 $\frac{1}{3}$ 吨均等流向 $4, 5$ 号结点，各流入 $\frac{1}{6}$ 吨。

最终 $4$ 号结点排出 $\frac{1}{6}+\frac{1}{6}=\frac{1}{3}$ 吨，$5$ 号结点排出 $\frac{1}{3}+\frac{1}{6}+\frac{1}{6}=\frac{2}{3}$ 吨。

【数据范围】

对于全部测试点，$1 \le n \le 10^5$，$1 \le m \le 10$，$0 \le d_i \le 5$。

数据保证污水从接收口流向最终排水口中途不超过 $10$ 个中间结点（接收口和最终排水口不算在内）。