T454242 「2024 百度之星选拔赛」明日之盛、昨日之俗
题目描述
幻想乡是一个有 $n$ 个点和 $m$ 条有向边的 **有向无环图**。图中每条边的 **边权长度为 $1$**,且 **图中可能存在重边**。
洩矢诹访子这天难得出门,想在幻想乡各地散散步。 她会在幻想乡中选择任意一条路径,所有路径的选择是等概率的。选择路径的起点和终点可以相同。
定义两条路径不同当且仅当两条路径至少经过一条不同的边。路径经过的节点序列相同,但是经过的边不同,也看作不同的路径(图中可能存在重边)。
现在,请你求出洩矢诹访子选择的路径长度的期望。
由于期望的计算过程可能涉及比较大的计算,你需要将答案对 $998244353$ 取模。
输入格式
第一行输入两个整数 $n,m$ $\;$ ($1 \le n \le 10^5$, $1 \le m \le 7 \times 10^5$),分别表示点数和边数。
接下来 $m$ 行,每行输入两个整数 $u, v$ $\;$ ($1 \le u, v \le n, u\not = v$),表示 $u$ 到 $v$ 有一条有向边。
输出格式
输出一行一个整数,表示选择的路径长度的期望,答案对 $998244353$ 取模后的值。
说明/提示
### 样例解释
样例1,2,3的答案分别为 $\dfrac{3}{8}$,$\dfrac{11}{13}$。
保证数据不会出现除以零的情况。