Signal Strength

Net Profits Incorporated has announced a new generation of network switching devices that support high-speed, instantly reconfigurable networks across long distances.

Each network is built from a new kind of switch. A switch watches several input lines, locks on to the strongest signal it receives, and forwards that signal to every output line connected to its output ports.

Because the connecting lines are long, signal loss is a major concern, and the switches themselves add further loss. To fight both, some switches carry amplifiers. To prevent destructive feedback, switches with amplifiers are never wired into a cycle in which their output could reach their own input, even indirectly.

Write a program that predicts the effective signal strength received at one point of a network when a signal is started at another point. You are given a network of $N$ switches ($1 \le N \le 1000$), numbered from $0$. Each switch has a multiplier telling how much weaker or stronger its output is than the strongest input reaching it. A switch without an amplifier multiplies the strength by a factor of at least $0.1$. A switch with an amplifier may multiply the strength by a factor as large as $5.0$.

You are also given the connecting lines. Each line has a multiplier describing how much weaker the signal is at the end of the line than when it entered; these line multipliers are at least $0.1$ and at most $1.0$.

The input contains one or more networks.

Each network starts with a line holding a single integer $N$, the number of switches; the switches are numbered starting at $0$. A non-positive value of $N$ marks the end of the input and is not itself a network.

The next $N$ lines describe the switches in order. Each line begins with a floating-point number, the strength multiplier of that switch, followed by an integer $k$, the number of lines attached to that switch's output. Then come $k$ pairs of numbers, one per output line: the first value of a pair is the number of the switch that receives the line as an input, and the second value is a floating-point multiplier for the signal loss along that line.

For each network, print one line

Network M: X

where $M$ is the network's number (starting at $1$) and $X$ is the signal strength at the output of switch $N-1$ when a signal of strength $1.0$ is applied to (all) inputs of switch $0$. If no signal ever reaches the output of switch $N-1$, then $X$ is $0$. Print $X$ with two digits after the decimal point.