#1325. 游走

游走

题目描述

B 城可以看作一个有 nn 个点 mm 条边的有向无环图。可能存在重边。

zbw 在 B 城随机游走,他会在所有路径中随机选择一条路径,选择所有路径的概率相等。路径的起点和终点可以相同。

定义一条路径的长度为经过的边数,你需要求出 zbw 走的路径长度的期望,答案对 998244353998244353 取模。

输入格式

第一行两个整数 n,mn,m。

接下来 mm 行,每行两个整数 x,yx,y,表示存在一条从 xx 到 yy 的有向边。

输出格式

一行一个整数,表示答案对 998244353998244353 取模后的值。

样例

3 2
1 2
3 2
199648871
6 5
1 3
2 3
3 4
4 5
4 6
630470119
5 6
1 2
1 3
4 5
3 4
3 5
2 4
887328315

题目来源:洛谷 P6154