Lisa

用所有路径的长度的和除以所有路径的种类就可以了.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int n,m;
int x,y;
int head[100005];
struct ed{
    int to;
    int ne;
}ed[700001];
int f[1000001];
int g[1000001];
int cnt[100001];
int mod=998244353;
int du[1000001];
int vis[1000001];
int p;
int qp(int bas,int mi){
    int ans=1;
    while(mi){
        if(mi&1){
            ans*=bas;
            ans%=mod;
        }
        bas*=bas;
        bas%=mod;
        mi>>=1;
    }
    return ans;
}
void add(int f,int to){
    ed[++p].to=to;
    ed[p].ne=head[f];
    head[f]=p;
    return ;
}
void dfs(int x){
    vis[x]=1;
    for(int i=head[x];i;i=ed[i].ne){
        int v=ed[i].to;
        g[v]=(g[v]+g[x])%mod;
        f[v]=(f[v]+f[x]+g[x])%mod;
        du[v]--;
        if(du[v]==0){
            dfs(v);
        }
    }
}
int sum1,sum2;
signed main(){
    read(n);read(m);
    for(int i=1;i<=m;++i){
        read(x);read(y);
        add(x,y);
        du[y]++;
    }
    for(int i=1;i<=n;++i){
        g[i]=1;
    }
    for(int i=1;i<=n;++i){
        if(!du[i]&&!vis[i]){
            dfs(i);
        }
    }
    for(int i=1;i<=n;++i){
        sum1+=g[i];sum1%=mod;
        sum2+=f[i];sum2%=mod;
    }

    cout<<sum2*qp(sum1,mod-2)%mod;
    return 0;
}