[中山市选2011]杀人游戏

一名冷血杀手潜入了 Na-wiat，并伪装成平民。警察希望从 $N$ 个人中找出杀手。

警察可以选择查证任意一个人。如果被查证者是平民，他会告诉警察自己认识的人中谁是杀手、谁是平民；如果被查证者是杀手，杀手就会将警察杀死。

现在，警察已经掌握了每个人认识哪些人。每个人成为杀手的概率均相同。请制定最优的查证方案，使警察在保证自身安全的同时确定杀手身份的概率最大，并求出这一最大概率。

输入格式

第一行包含两个整数 $N,M$ ，分别表示人数和认识关系的数量。

接下来 $M$ 行，每行包含两个整数 $x,y$ ，表示 $x$ 认识 $y$ 。该关系不一定是双向的，即 $y$ 不一定认识 $x$ 。

输出一行一个实数，表示警察在保证自身安全的同时确定杀手身份的最大概率，保留小数点后 $6$ 位。

0.800000

警察只需要查证编号为 $1$ 的人。如果编号为 $1$ 的人是杀手，警察就会被杀；否则，他会告诉警察编号为 $2,3,4,5$ 的人中谁是杀手。

编号为 $1$ 的人是杀手的概率为 $0.2$ ，因此警察能够确定杀手身份且不被杀的概率为 $0.8$ 。

本题为 2011 年中山市选试题「杀人游戏」，题面与测试数据整理自 BZOJ 2438。

0.800000