Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)

    # 辺を除かなかったときの期待値dp
    dp=[None]*n
    dp[-1]=0
    def dfs(v):
        if(dp[v] is not None): return dp[v]
        res=0
        deg=len(E[v])
        for nv in E[v]:
            res+=dfs(nv)
        dp[v]=res/deg+1
        return dp[v]

    ans=dfs(0)

    # 辺を除いたときの期待値dp
    dp1=[None]*n
    v0,w0=-1,-1
    def dfs1(v):
        if(dp1[v] is not None): return dp1[v]
        res=0
        deg=len(E[v])
        for nv in E[v]:
            if((v,nv)==(v0,w0)):
                deg-=1
            else:
                res+=dfs1(nv)
        dp1[v]=res/deg+1
        return dp1[v]

    for v0 in range(n):
        if(len(E[v0])<=1): continue
        dp1=[None]*n
        dp1[-1]=0
        w0=max((dp[w0],w0) for w0 in E[v0])[1]
        ans=min(ans,dfs1(0))

    print(ans)
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1;
        E[s].append(t)
    dp=[0]*n
    for v in range(n-2,-1,-1):
        res=0
        for nv in E[v]: res+=dp[nv]
        dp[v]=1+res/len(E[v])
    ans=dp[0] # 辺を消さなかった時のscore

    # 各 v に対し、削除する辺 v→u は、dp[u]が最大のもの
    for v in range(n-1):
        if(len(E[v])==1): continue
        u=max(*((dp[nv],nv) for nv in E[v]))[1]
        # vu を削除したときの期待値DPを行う
        dp2=[0]*n
        for x in range(n-2,-1,-1):
            res=0
            for nx in E[x]:
                if(x==v and nx==u): continue
                res+=dp2[nx]
            if(v!=x):
                dp2[x]=1+res/len(E[x])
            else:
                dp2[x]=1+res/(len(E[x])-1)
        ans=min(ans,dp2[0])
    print(ans)
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1;
        E[s].append(t)
    dp=[0]*n
    for v in range(n-2,-1,-1):
        res=0
        for nv in E[v]: res+=dp[nv]
        dp[v]=1+res/len(E[v])
    ans=dp[0] # 辺を消さなかった時のscore

    # 各 v に対し、削除する辺 v→u は、dp[u]が最大のもの
    for v in range(n-1):
        if(len(E[v])==1): continue
        u=max(*((dp[nv],nv) for nv in E[v]))[1]
        # vu を削除したときの期待値DPを行う
        dp2=[0]*n
        for x in range(n-2,-1,-1):
            res=0
            for nx in E[x]:
                if(x==v and nx==u): continue
                res+=dp2[nx]
            if(v!=x):
                dp2[x]=1+res/len(E[x])
            else:
                dp2[x]=1+res/(len(E[x])-1)
        ans=min(ans,dp2[0])
    print(ans)
resolve()

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1;
        E[s].append(t)
    dp=[0]*n
    for v in range(n-2,-1,-1):
        res=0
        for nv in E[v]: res+=dp[nv]
        dp[v]=1+res/len(E[v])
    ans=dp[0] # 辺を消さなかった時のscore

    # 各 v に対し、削除する辺 v→u は、dp[u]が最大のもの
    for v in range(n-1):
        if(len(E[v])==1): continue
        u=max(*((dp[nv],nv) for nv in E[v]))[1]
        # vu を削除したときの期待値DPを行う
        dp2=[0]*n
        for x in range(n-2,-1,-1):
            res=0
            for nx in E[x]:
                if(x==v and nx==u): continue
                res+=dp2[nx]
            if(v!=x):
                dp2[x]=1+res/len(E[x])
            else:
                dp2[x]=1+res/(len(E[x])-1)
        ans=min(ans,dp2[0])
    print(ans)
resolve()