The drainage system is an extremely important part of a city.

One day, little C got the diagram of a city drainage system. The drainage system is made of $n$ drainage nodes labelled from $1$ to $n$ and several unidirectional drainage pipes. Each drainage node has several pipes to collect the sewage from other drainage nodes, which we call input pipes, and there are also several pipes to discharge sewage to other drainage nodes, which we call output pipes.

There are $m$ sewage input ports in the nodes of the drainage system labelled from $1$ to $m$; sewage can only flow into the drainage system from these input ports, and there are input pipes at these nodes. There are also several output drains in the drainage system, which transports the sewage to where sewage is treated, and the node without the output pipe can be regarded as an output drain.

Initially, each of the sewage input ports received $1$ ton of sewage. After the sewage enters each node, it will flow equally from each output pipe of the current node to other drainage nodes, and finally, the output drain will discharge the sewage out of the system.

Little C wants to know how much sewage is discharged from each output drain in the city's drainage system. The city's drainage system is scientifically designed, and the pipes will not form a loop; that is, there will be no circulation of sewage.

Input Specification

The first line contains two space-separated integers $n$ and $m$, representing the total number of drainage nodes and the total number of input ports, respectively.

The $i^{\text{th}}$ of the next $n$ lines represents all of the output pipes of node $i$. The first integer on each line, $d_i$, represents the number of output pipes that node $i$ has; the next $d_i$ space-separated integers, $a_1,a_2,\dots ,a_d$, represent the target nodes of each output pipe. It is guaranteed that there will not be two pipes with the same start and target node.

Output Specification

Output the volume of sewage discharged from each output drain in ascending order of node label. The volume is output in fractional form; that is, each line output should contain two integers $p$ and $q$ separated by a single space; indicating that the volume of sewage discharged from the output drain is $\frac{p}{q}$, where $p$ and $q$ are co-prime.

Sample Input

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

Sample Output

1 3
2 3

Explanation for Sample

Node $1$ is an input port. Node $4$ and node $5$ have no output pipe; therefore, they are output drains.

After $1$ ton of sewage flows into node $1$, it flows equally to nodes $2,3,5$, and each of the three nodes flows into $\frac{1}{3}$ tons of sewage.

The $\frac{1}{3}$ tons of sewage flowing into the node $2$ will equally flow to the nodes $4,5$, and each of the two nodes will flow into $\frac{1}{6}$ tons of sewage.

The $\frac{1}{3}$ tons of sewage flowing into the node $3$ will equally flow to the nodes $4,5$, and each of the two nodes will flow into $\frac{1}{6}$ tons of sewage.

Finally, node $4$ discharges $\frac{1}{6}+\frac{1}{6}=\frac{1}{3}$ tons of sewage, and node $5$ discharges $\frac{1}{3}+\frac{1}{6}+\frac{1}{6}=\frac{2}{3}$ tons of sewage.

Additional Samples

Additional samples can be found here.

• Sample 2 (water2.in and water2.ans).
• Sample 3 (water3.in and water3.ans).

Constraints

Test Case	$n\le$	$m\le$
$1\sim 3$	$10$	$1$
$4\sim 6$	${10}^3$	$1$
$7\sim 8$	${10}^5$	$1$
$9\sim 10$	${10}^5$	$10$

For all test cases, $1\le n\le {10}^5$, $1\le m\le 10$, $0\le d_i\le 5$.

It's guaranteed that sewage will not pass through more than $10$ drainage nodes in the process of flowing from an input port to an output drain (the input port and the output drains are not counted).

Problem translated to English by Tommy_Shan.