[中山市选] 杀人游戏

题目描述

一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 $N$ 个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。

问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？

输入格式

第一行有两个整数 $N,M$。

接下来有 $M$ 行，每行两个整数 $x,y$，表示 $x$ 认识 $y$（$y$ 不一定认识 $x$，例如 President 同志）。

输出格式

仅包含一行一个实数，保留小数点后面 $6$ 位，表示最大概率。

输入输出样例

输入样例 #1

5 4 
1 2 
1 3 
1 4 
1 5

输出样例 #1

0.800000

说明/提示

警察只需要查证 $1$。假如 $1$ 是杀手，警察就会被杀。假如 $1$ 不是杀手，他会告诉警察 $2,3,4,5$ 谁是杀手。而 $1$ 是杀手的概率是 $0.2$，所以能知道谁是杀手但没被杀的概率是 $0.8$。

对于 $100\%$ 的数据有 $1\le N\le 1\times 10^5$，$0\le M\le 3\times 10^5$。