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 drainage nodes labelled from to 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 sewage input ports in the nodes of the drainage system labelled from to ; 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 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 and , representing the total number of drainage nodes and the total number of input ports, respectively.
The of the next lines represents all of the output pipes of node . The first integer on each line, , represents the number of output pipes that node has; the next space-separated integers, , 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 and separated by a single space; indicating that the volume of sewage discharged from the output drain is , where and 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 is an input port. Node and node have no output pipe; therefore, they are output drains.
After ton of sewage flows into node , it flows equally to nodes , and each of the three nodes flows into tons of sewage.
The tons of sewage flowing into the node will equally flow to the nodes , and each of the two nodes will flow into tons of sewage.
The tons of sewage flowing into the node will equally flow to the nodes , and each of the two nodes will flow into tons of sewage.
Finally, node discharges tons of sewage, and node discharges tons of sewage.
Additional Samples
Additional samples can be found here.
- Sample 2 (
water2.in
andwater2.ans
). - Sample 3 (
water3.in
andwater3.ans
).
Constraints
Test Case | ||
---|---|---|
For all test cases, , , .
It's guaranteed that sewage will not pass through more than 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 .
Comments
The denominator can exceed .