}
else
{
dpx[now]+=dpx[to]/double(cnt[now]);
}
}
}
if(ins[now])
{
double temp = 2.0/double(cnt[now]+2.0);
dpx[now] += nn*temp;
}
else
{
double temp = 1.0/double(cnt[now]+1.0);
dpx[now] += nn*temp;
}
return ;
}
void df2(int now)
{
vis[now]=true;
int to;
for(int i=0;i
to = g[now][i];
if(!ins[to] && !vis[to])
{
dpy[to] = dpy[now]/double(cnt[now]);
dpy[to] += nn*double(cnt[to])/double(cnt[to]+1.0);
if(ins[now])
{
dpy[to]+=(dps[now]-dpx[to])/(cnt[now]+1.0);
}
else
{
dpy[to]+=(dps[now]-dpx[to])/double(cnt[now]);
}
df2(to);
}
}
if(!cnt[now])
{
dp[now] = dpy[now];
}
return ;
}
void find()
{
int now=s[0];
int to;
vis[now] = true;
bool ok;
while(true)
{
ok = false;
for(int i=0;i
to = g[now][i];
if(ins[to] && !vis[to])
{
vis[to]=true;
s.pb(to);
now = to;
ok = true;
break;
}
}
if(!ok) break;
}
return ;
}
void start()
{
/* MM(f,0);
MM(t,0);
MM(dfn,0);
MM(low,0);
MM(ins,false);*/
for(int i=0;i<=n;i++)
{
f[i]=0;
t[i]=0;
low[i]=0;
ins[i]=false;
}
s.clear();
df=nf=1;
tarjan(1);
nf--;
for(int i=1;i<=n;i++)
{
v[f[i]].pb(i);
}
int tv;
for(int i=1;i<=nf;i++)
{
if(v[i].size()>1)
{
tv=i;
break;
}
}
s.clear();
tot = v[tv].size();
// MM(ins,false);
// MM(vis,false);
for(int i=0;i<=n;i++)
{
ins[i]=false;
vis[i]=false;
}
for(int i=0;i
ins[v[tv][i]] = true;
}
s.pb(v[tv][0]);
find();
int now,to;
MM(yes,0);
for(int i=0;i
now = s[i];
for(int j=0;j
to = g[now][j];
if(!ins[to])
{
yes[i]++;
}
}
}
MM(go,0);
MM(back,0);
int ss = s.size();
for(int i=0;i
if(yes[i])
{
go[i][(i+1)%ss]=1.0/(yes[i]+1.0);
back[i][(i-1+ss)%ss]=1.0/(yes[i]+1.0);
}
else
{
go[i][(i+1)%ss]=1.0;
back[i][(i-1+ss)%ss]=1.0;
}
}
for(int u=2;u
for(int i=0;i
go[i][(i+u)%ss]=go[i][(i+u-1)%ss]*go[(i+u-1)%ss][(i+u)%ss];
back[i][(i-u+ss)%ss]=back[i][(i-(u-1)+ss)%ss]*back[(i-(u-1)+ss)%ss][(i-u+ss)%ss];
}
}
/* MM(vis,false);
MM(dpx,0);
MM(dpy,0);
MM(dp,0);
MM(dps,0);
MM(cnt,0);*/
for(int i=0;i<=n;i++)
{
vis[i]=false;
dpx[i]=0;
dpy[i]=0;
dp[i]=0;
dps