这个题有点味道.
考虑在一个SCC中,任意一个点的身份知道了,那么SCC中的所有点身份就都知道了.所以SCC和点是等价的,我们可以先跑一遍tarjan缩点,得到一个DAG.
考虑任意一条$u->v$的路径,如果$u$是杀手那没办法就是凉凉,否则这条路径上所有人的身份都会明确.所以我们必须”冒险访问”(在不明身份的情况下访问,可能导致警察被干掉)的点只有入度为0的点,设有$cnt$个.也就是说失败的概率就是$\frac{cnt}{n}$.
事实上这是不准确的.试想,如果$n-1$个人都明确了是平民,那么剩下那个只能是杀手了.所以如果存在某个入度为0的点$u$满足它能直接到达的点入度都$>1$(即不访问$u$,通过访问其它点就能得到这些点的信息),那么这个$u$就不必冒险访问,将$cnt-1$(注意,这个操作只能使用一次).
时间复杂度$O(n+m)$

/**********/省略快读
#define MAXN 100011
#define MAXM 300011
struct Graph
{
    struct Edge
    {
        ll v,nxt;
    }e[MAXM];
    ll cnt=0,last[MAXN];
    void adde(ll u,ll v)
    {
        e[++cnt].v=v;
        e[cnt].nxt=last[u],last[u]=cnt;
    }
}e,se;//e是原图,se是缩点后的图

ll dfn[MAXN],low[MAXN],cur=0,scc[MAXN],size[MAXN],scnt=0;
ll s[MAXN],top=0;
bool ins[MAXN];
void tarjan(ll u)//tarjan缩点
{
    dfn[u]=low[u]=++cur;
    s[++top]=u;ins[u]=1;
    for (int i = e.last[u]; i  ; i=e.e[i].nxt)
    {
        ll v=e.e[i].v;
        if (!dfn[v])
        {
            tarjan(v);
            umin(low[u],low[v]);
        }
        else if (ins[v])umin(low[u],dfn[v]);
    }
    if (low[u]==dfn[u])
    {
        ++scnt;
        while (s[top]!=u)
        {
            ++size[scnt];
            scc[s[top]]=scnt;
            ins[s[top]]=0;
            --top;
        }
        ++size[scnt];
        scc[s[top--]]=scnt;
        ins[u]=0;
    }
}

ll n,m,ind[MAXN],outd[MAXN];
int main()
{
    n=read(),m=read();
    for (int i = 1; i <= m; ++i)
    {
        ll u=read(),v=read();
        e.adde(u,v);
    }
    for (int i = 1; i <= n; ++i)
        if(!dfn[i])tarjan(i);
    for (int u = 1; u <= n; ++u)//重建图顺便统计入度
        for (int i = e.last[u]; i ; i=e.e[i].nxt)
        {
            ll v=e.e[i].v;
            if (scc[u]!=scc[v])
            {
                ++ind[scc[v]];se.adde(scc[u],scc[v]);
            }
        }
    ll cnt=0;//入度为0的点
    bool flag=0;//可以不访问,排除法就能推断出的点
    for (int u = 1; u <= scnt; ++u)
    {
        if (!ind[u])
        {
            ++cnt;
            if (size[u]>1||flag)continue;
            bool tmp=1;
            for (int i = se.last[u]; i ; i=se.e[i].nxt)
                if (ind[se.e[i].v]==1)tmp=0;
            flag|=tmp;
        }
    }
    printf("%.6lf",1-double(cnt-flag)/n);
    return 0;
}