P7113 [NOIP2020] Drainage System

For a city, the drainage system is an extremely important part. One day, Xiao C obtained the design blueprint of a city's drainage system. The drainage system consists of $n$ drainage nodes (numbered from $1 \sim n$) and several one-way drainage pipes. Each drainage node has some pipes to collect sewage from other drainage nodes (called the incoming pipes of this node), and also some pipes to discharge sewage to other drainage nodes (called the outgoing pipes of this node). Among the nodes of the drainage system, there are $m$ sewage inlets, with indices $1, 2, \ldots , m$. Sewage can only enter the drainage system from these inlets, and these nodes have no incoming pipes. The drainage system also has some final outlets that transport sewage to the sewage treatment plant. A node with no outgoing pipes can be regarded as a final outlet. Now, each sewage inlet receives $1$ ton of sewage. After sewage enters a node, it will be evenly distributed along each outgoing pipe of the current node to other drainage nodes, while final outlets will discharge the sewage out of the system. Now Xiao C wants to know how much sewage each final outlet will discharge in this city's drainage system. The design of the drainage system is sound: the pipes will not form cycles, i.e., there will be no circular flow of sewage.

The first line contains two integers $n, m$ separated by a single space, representing the number of drainage nodes and the number of inlets. The next $n$ lines describe the outgoing pipes of each node. In the $i$-th line, the first integer $d_i$ denotes the number of outgoing pipes. Then $d_i$ integers $a_1, a_2, \ldots , a_{d_i}$ separated by single spaces follow, indicating the target drainage nodes of these pipes in order. It is guaranteed that there will not be two pipes with the same start node and the same target node.

Output several lines. In increasing order of node index, output the amount of sewage discharged by each final outlet. The amount should be printed as a fraction: each line outputs two integers $p$, $q$ separated by a single space, meaning the discharged amount is $\frac{p}{q}$. It is required that $p$ and $q$ are coprime. When $q = 1$, you still need to output $q$.

**[Sample #1 Explanation]** Node $1$ is an inlet, and nodes $4, 5$ have no outgoing pipes, so they are final outlets. After $1$ ton of sewage flows into node $1$, it is evenly distributed to nodes $2, 3, 5$, so each of the three nodes receives $\frac{1}{3}$ ton of sewage. The $\frac{1}{3}$ ton of sewage that flows into node $2$ will be evenly distributed to nodes $4, 5$, so each of the two nodes receives $\frac{1}{6}$ ton of sewage. The $\frac{1}{3}$ ton of sewage that flows into node $3$ will be evenly distributed to nodes $4, 5$, so each of the two nodes receives $\frac{1}{6}$ ton of sewage. Finally, node $4$ discharges $\frac{1}{6} + \frac{1}{6} = \frac{1}{3}$ ton of sewage, and node $5$ discharges $\frac{1}{3} + \frac{1}{6} + \frac{1}{6} = \frac{2}{3}$ ton of sewage. **[Constraints]** | Test Point ID | $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 points, it is guaranteed that $1 \le n \le {10}^5$, $1 \le m \le 10$, and $0 \le d_i \le 5$. The testdata guarantees that in the process of sewage flowing from an inlet to a final outlet, it will not pass through more than $10$ intermediate drainage nodes (i.e., excluding the inlet and the final outlet). Translated by ChatGPT 5