1 #include<cstdio>
2 #include<cstring>
3 #include<ctime>
4 #include<queue>
5 #include<algorithm>
6 #include<iostream>
7 #define dd double
8 #define mem(a,b) memset(a,b,sizeof(a))
9 using namespace std;
10 const int N=100500;
11 int minn(int a,int b){return a<b?a:b;}
12 bool ok(int a,int b){return a>b;}
13 int read()
14 {
15 int ans=0;char q=getchar();
16 while(q<'0'||q>'9')q=getchar();
17 while(q>='0'&&q<='9'){ans=ans*10+q-'0';q=getchar();}
18 return ans;
19 }
20 struct son
21 {
22 int v,next;
23 };
24 son a1[N<<2],ayuan[N<<2];
25 int first[N<<2],firstyuan[N<<2],e,eyuan;
26 void add(int u,int v)
27 {
28 a1[e].v=v;
29 a1[e].next=first[u];
30 first[u]=e++;
31 }
32 void addyuan(int u,int v)
33 {
34 ayuan[eyuan].v=v;
35 ayuan[eyuan].next=firstyuan[u];
36 firstyuan[u]=eyuan++;
37 }
38
39 int dfn[N],low[N],vis[N],now;
40 int dui[N],sum,size[N];
41 int zhan[N<<3],he;
42 void tan(int x)
43 {
44 //printf("x=%d
",x);
45 dfn[x]=low[x]=++now;
46 zhan[++he]=x;vis[x]=1;
47 for(int i=firstyuan[x];i!=-1;i=ayuan[i].next)
48 {
49 int temp=ayuan[i].v;
50 //printf("temp=%d
",temp);
51 if(dfn[temp]==-1)
52 {
53 tan(temp);
54 low[x]=minn(low[x],low[temp]);
55 }
56 else
57 if(vis[temp])
58 low[x]=minn(low[x],dfn[temp]);
59 }
60 if(dfn[x]==low[x])
61 {
62 ++sum;int temp;
63 while(1)
64 {
65 temp=zhan[he--];
66 vis[temp]=0;
67 dui[temp]=sum;
68 ++size[sum];
69 if(temp==x)
70 break;
71 }
72 }
73 }
74
75 int n,m;
76 int u,o,p,hh;
77 int ind[N],zhen[N];
78 int judge[N];
79 bool flag[N];
80 //好像只需找出真点
81 void dfs(int x,int fa)
82 {
83 if(judge[x]!=-2)
84 zhen[fa]+=size[x];
85 else
86 return ;
87 for(int i=first[x];i!=-1;i=a1[i].next)
88 dfs(a1[i].v,fa);
89 }
90
91 dd mi(dd a,int c)
92 {
93 dd ans=1;
94 while(c)
95 {
96 if(c&1)
97 ans*=a;
98 a=a*a;
99 c>>=1;
100 }
101 return ans;
102 }
103
104 /*void out11()
105 {
106 printf("hh=%d sum=%d
",hh,sum);
107 for(int i=1;i<=sum;++i)
108 printf("%d ",zhen[i]);
109 printf("
");
110 }*/
111
112 int main(){
113 //freopen("killer7.in","r",stdin);
114 //freopen("killer.out","w",stdout);
115 //freopen("1.txt","r",stdin);
116 mem(firstyuan,-1);
117 mem(judge,-1);
118 mem(dfn,-1);
119 mem(first,-1);
120 n=read();m=read();
121 for(int i=1;i<=m;++i)
122 {
123 u=read();o=read();
124 addyuan(u,o);
125 }
126 for(int i=1;i<=n;++i)
127 if(dfn[i]==-1)
128 tan(i);
129 //cout<<0;
130
131 for(int i=1;i<=n;++i)
132 {
133 for(int j=firstyuan[i];j!=-1;j=ayuan[j].next)
134 {
135 int temp=ayuan[j].v;
136 if(dui[i]==dui[temp])continue;//不能自己连
137 add(dui[i],dui[temp]);
138 if(judge[dui[temp]]==-1)
139 judge[dui[temp]]=dui[i];
140 else
141 if(judge[dui[temp]]!=dui[i]&&judge[dui[temp]]!=-2)
142 judge[dui[temp]]=-2;
143 }
144 }
145
146 hh=0;
147
148 for(int i=1;i<=sum;++i)
149 if(judge[i]==-1)
150 {
151 dfs(i,i);
152 ++hh;
153 }
154 sort(zhen+1,zhen+1+sum,ok);
155 if(zhen[hh]==1)--hh;
156
157 //cout<<hh;
158 printf("%.6lf",1-hh*1.0/(dd)n);
159 //while(1);
160 return 0;
161 }
162
