Problem Description

A cold-blooded killer sneaks into Na-wiat and pretends to be a civilian. The police want to find out who the killer is among $N$ people. The police can verify people one by one. If the verified person is a civilian, they will tell the police, among the people they know, who is the killer and who is a civilian. If the verified person is the killer, the killer will kill the police.

Now the police know, for every person, whom they know. Everyone could be the killer, and the probability that each person is the killer is the same.

Question: Under an optimal strategy, what is the maximum possible probability that the police can both guarantee their own safety and know who the killer is?

Input Format

The first line contains two integers $N, M$.

The next $M$ lines each contain two integers $x, y$, meaning that $x$ knows $y$ ($y$ does not necessarily know $x$, for example, Comrade President).

Output Format

Output only one real number in a single line, rounded to $6$ digits after the decimal point, representing the maximum probability.

5 4 
1 2 
1 3 
1 4 
1 5 

0.800000

Hint

The police only need to verify person $1$. If $1$ is the killer, the police will be killed. If $1$ is not the killer, they will tell the police, among $2, 3, 4, 5$, who is the killer. Since the probability that $1$ is the killer is $0.2$, the probability that the police can know who the killer is without being killed is $0.8$.

For $100\%$ of the testdata, $1 \le N \le 1 \times 10^5$, $0 \le M \le 3 \times 10^5$.

Translated by ChatGPT 5