[中山市选] 杀人游戏
题目描述
一位冷血的杀手潜入Na-wiat,并假装成平民。警察希望能在$N$个人里面,查出谁是杀手。警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他认识的人,谁是杀手,谁是平民。假如查证的对象是杀手,杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。
问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多少?
输入输出格式
输入格式
第一行有两个整数 $N,M$。
接下来有 $M$ 行,每行两个整数 $x,y$,表示 $x$ 认识 $y$($y$ 不一定认识 $x$ ,例如President同志) 。
注:原文zz敏感内容已替换
输出格式
仅包含一行一个实数,保留小数点后面 $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≤N≤100000,0≤M≤300000$。