URI Online Judge | 1809

Secret Agents

By Unknown Brazil

Timelimit: 0

All people who have seen the movies or series of espionage like 007, Mission Impossible or Hawaii 5-0, know that some countries of the world keeps groups of undercover intelligence agents in governments and organizations in the Middle East , South America and Eastern Europe .

An intelligence service has n agents scattered in a not very friendly country. Each agent knows other agents and has specific procedures to arrange a secret meeting with each one of them. Coded messages are usually exchanged to arrange such meetings. Given two agents i and j who known each other, there is a certain probability pij of a message exchanged between them is intercepted by hostile individuals.

From time to time, the leader of the intelligence service needs to disseminate confidential information to all his field agents. To do so, he uses the messaging mechanism of the agents, ie, he contacts some of these agents he knows and they are responsible for propagating the information so that the probability of interception P is minimal. As you can see, the service is so secret that not even the leader knows all his subordinate agents. Your task in this problem is to build a program that calculates P.


Your program should be prepared to work on different scenarios, ie, several broadcasts confidential information in various countries. Each scenario is described in the following way. The first line specifies the number of agents in the country, 0 < n ≤ 100, including the leader of the intelligence service, and the number of pairs of agents who are in the country and known each other, 0 ≤ m ≤ 4950. Each of the following m lines contains two integers i, j and a rational pij, 1 ≤ i, jn and 0 ≤ pij ≤ 1. Each line means that agents i and j know each other and that a message exchanged between them is intercepted with probability pij. A zero value for n indicates the end of the scenarios. You can assume that it will always be possible to transmit confidential information between all agents.


For each scenario the input, your program should print the text Cenario x, probabilidade de interceptacao = P, where x is the position of the respective scenario in the input file (numbered from 1) and P the probability of the information being disseminated to be intercepted. This probability should be printed with three decimal places. You must leave a blank line between each scenario.

Sample Input Sample Output

4 6

1 2 0.3

1 3 0.1

1 4 0.5

2 3 0.9

2 4 0.1

3 4 0.5

3 2

1 2 1.0

2 3 1.0

0 0

Cenario 1, probabilidade de interceptacao = 0.433

Cenario 2, probabilidade de interceptacao = 1.000