Problem Description

For a city, the drainage system is an extremely important component.

One day, Xiao C obtained the design diagram of the drainage system for a certain city. The drainage system consists of $n$ drainage nodes (numbered from $1$ to $n$) and several one-way drainage pipes. Each drainage node has several pipes to collect wastewater from other nodes (referred to as the node's collection pipes) and several pipes to discharge wastewater to other nodes (referred to as the node's discharge pipes).

Among the nodes of the drainage system, there are $m$ wastewater intake points, numbered $1, 2, \ldots, m$. Wastewater can only enter the system through these intake points, and these nodes do not have collection pipes. There are also several final discharge outlets in the system, which transport wastewater to the sewage treatment plant. Nodes without discharge pipes can be considered as final discharge outlets.

Now, each wastewater intake point receives $1$ ton of wastewater. Once wastewater enters each node, it will be evenly distributed from the current node's discharge pipes to other drainage nodes, and the final discharge outlets will expel the wastewater from the system.

Xiao C wants to know how much wastewater each final discharge outlet will expel in the city's drainage system. The city's drainage system is scientifically designed, and the pipes do not form loops, meaning there will be no situation where wastewater circulates in a loop.

Input Format

The first line contains two integers $n$ and $m$ separated by a single space. They represent the number of drainage nodes and the number of intake points, respectively.
The next $n$ lines describe the discharge pipes of each node. The $i$-th line begins with an integer $d_i$ indicating the number of discharge pipes, followed by $d_i$ integers $a_1, a_2, \ldots, a_{d_i}$ separated by single spaces, representing the target drainage nodes of the pipes.
It is guaranteed that there will not be two pipes with the same starting and ending nodes.

Output Format

Output several lines, listing the wastewater volume expelled by each final discharge outlet in ascending order of their numbers. The volume should be expressed as a fraction, with each line containing two integers $p$ and $q$ separated by a single space, indicating that the expelled wastewater volume is $\frac{p}{q}$. Ensure that $p$ and $q$ are coprime, and $q = 1$ should also be output as $q$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

1 3
2 3

Input Sample #2

See the attached file water/water2.in

Output Sample #2

See the attached file water/water2.ans

Input Sample #3

See the attached file water/water3.in

Output Sample #3

See the attached file water/water3.ans

Notes

[Sample #1 Explanation]

Node $1$ is the intake point, and nodes $4, 5$ do not have discharge pipes, so they are the final discharge outlets.
$1$ ton of wastewater enters node $1$ and is evenly distributed to nodes $2, 3, 5$, each receiving $\frac{1}{3}$ ton of wastewater.
The $\frac{1}{3}$ ton of wastewater entering node $2$ is evenly distributed to nodes $4, 5$, each receiving $\frac{1}{6}$ ton of wastewater.
The $\frac{1}{3}$ ton of wastewater entering node $3$ is evenly distributed to nodes $4, 5$, each receiving $\frac{1}{6}$ ton of wastewater.
Ultimately, node $4$ expels $\frac{1}{6} + \frac{1}{6} = \frac{1}{3}$ ton of wastewater, and node $5$ expels $\frac{1}{3} + \frac{1}{6} + \frac{1}{6} = \frac{2}{3}$ ton of wastewater.

[Data Range]

For all test cases, it is guaranteed that $1 \le n \le {10}^5$, $1 \le m \le 10$, and $0 \le d_i \le 5$.

The data ensures that the path of wastewater from an intake point to a final discharge outlet does not pass through more than $10$ intermediate drainage nodes (excluding the intake and final discharge outlets).

见题面 Input 部分

见题面 Output 部分