Description
一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，
查出谁是杀手。
警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他
认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手， 杀手将会把警察干掉。
现在警察掌握了每一个人认识谁。
每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。
问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多
少？
Input
第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如胡锦涛同志） 。
Output
仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。
Sample Input
5 4
1 2
1 3
1 4
1 5
1 2
1 3
1 4
1 5
Sample Output
0.800000
HINT
警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警
察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概
率是0.8。
对于 100%的数据有 1≤N ≤ 10 0000,0≤M ≤ 30 0000
改用guide……排版就变了……
缩环之后图会变成拓扑图，即是对于每个入度为0的联通块进行一次询问即可得知凶手
所以答案为(n-入度为0的联通块)/n
需要注意的是如果某块点数为1，且儿子块可由询问别的块确定，可以少询问一次……增加1/n的概率
program bzoj2438;
const
maxn=8000000;
var
now,tot,all,n,m,i,j,k,x,y,o:longint;
one:boolean;
ans:double;
ou,fin,dd,count,stack,dfn,low,belong,root:array [0..100001] of longint;
yes:array [0..100001] of boolean;
point,next:array [0..300001] of longint;
anti:array [0..maxn] of record
u,v:longint;
end;
procedure connect (u,v:longint);inline;
begin
inc(tot);
point[tot]:=v;
next[tot]:=root[u];
root[u]:=tot;
end;
procedure tarjan (now:longint);
var
i:longint;
begin
yes[now]:=true;
inc(tot);
stack[tot]:=now;
dfn[now]:=tot;
low[now]:=tot;
i:=root[now];
while i<>0 do
begin
if belong[point[i]]=0 then
if not yes[point[i]] then
begin
tarjan(point[i]);
if low[point[i]]<low[now] then
low[now]:=low[point[i]];
end
else
if dfn[point[i]]<low[now] then
low[now]:=dfn[point[i]];
i:=next[i];
end;
if dfn[now]=low[now] then
begin
inc(all);
while tot>=dfn[now] do
begin
inc(count[all]);
belong[stack[tot]]:=all;
dec(tot);
end;
end;
end;
function hash (x,y:longint):longint;inline;
var
i:longint;
begin
i:=(int64(x)*y+x*568+y*124) mod maxn;
while (anti[i].u<>0)and((anti[i].u<>x)or(anti[i].v<>y)) do
begin
inc(i);
if i=maxn then i:=0;
end;
exit(i);
end;
begin
read(n,m);
if n=0 then
begin
ans:=1;
writeln(ans:0:6);
halt;
end;
for i:=1 to m do
begin
read(x,y);
connect(x,y);
end;
tot:=0;
all:=0;
for i:=1 to n do
if not yes[i] then
tarjan(i);
for i:=1 to n do
begin
k:=root[i];
while k<>0 do
begin
if belong[point[k]]<>belong[i] then
begin
inc(dd[belong[point[k]]]);
o:=hash(belong[i],belong[point[k]]);
if anti[o].u=0 then
begin
inc(fin[belong[point[k]]]);
anti[o].u:=belong[i];
anti[o].v:=belong[point[k]];
end;
end;
k:=next[k];
end;
end;
for i:=1 to n do
begin
k:=root[i];
while k<>0 do
begin
if fin[belong[point[k]]]=1 then
ou[belong[i]]:=1;
k:=next[k];
end;
end;
ans:=n;
one:=false;
for i:=1 to all do
if dd[i]=0 then
begin
ans:=ans-1;
if (count[i]=1)and(ou[i]=0) then one:=true;
end;
if one then ans:=ans+1;
ans:=ans/n;
writeln(ans:0:6);
end.