Drainage System Flow Simulation

In a city, the drainage system is of utmost importance. The system consists of \(n\) drainage nodes (numbered from \(1\) to \(n\)) and several one-way drainage pipes. Each node may have several incoming pipes (used to collect sewage from other nodes) and several outgoing pipes (used to discharge sewage to other nodes).

There are \(m\) sewage inlets, numbered from \(1\) to \(m\). Sewage enters the system only through these inlets, and they do not have any incoming pipe. Some nodes, which do not have any outgoing pipes, act as final drainage outlets and discharge the sewage out of the system to the treatment plant.

Initially, each sewage inlet receives \(1\) ton of sewage. When a node receives sewage, it distributes the sewage equally among all its outgoing pipes. Since the drainage system is designed scientifically, the pipes form a directed acyclic graph (DAG), meaning there are no cycles.

Your task is to calculate the amount of sewage discharged by each final drainage outlet.

inputFormat

The first line contains three integers \(n\), \(m\), and \(p\) where \(n\) is the number of nodes, \(m\) is the number of sewage inlets, and \(p\) is the number of drainage pipes.

Each of the next \(p\) lines contains two integers \(u\) and \(v\), indicating there is a one-way pipe from node \(u\) to node \(v\).

outputFormat

For every final drainage outlet (i.e. node with no outgoing pipes), output a line containing two values: the node number and the amount of sewage it discharges, formatted to 6 decimal places. The final outlets should be listed in increasing order of their node numbers.

sample

5 2 4
1 3
1 4
2 3
3 5

4 0.500000
5 1.500000