题目描述
Problem Background
zbw is wandering around City B.
Problem Description
City B can be considered as a directed acyclic graph with $n$ vertices and $m$ edges. There may be multiple edges between the same pair of vertices.
zbw randomly walks in City B. He randomly selects a path among all possible paths with equal probability. The starting and ending points of a path can be the same.
The length of a path is defined as the number of edges traversed. You need to calculate the expected length of the path zbw walks, and the answer should be modulo $998244353$.
Input Format
The first line contains two integers $n$ and $m$.
The next $m$ lines each contain two integers $x$ and $y$, indicating a directed edge from $x$ to $y$.
Output Format
A single line containing one integer, which is the answer modulo $998244353$.
Sample Input and Output
Sample Input #1
3 2
1 2
3 2
Sample Output #1
199648871
Sample Input #2
6 5
1 3
2 3
3 4
4 5
4 6
Sample Output #2
630470119
Sample Input #3
5 6
1 2
1 3
4 5
3 4
3 5
2 4
Sample Output #3
887328315
Notes
The answers for the samples are $\dfrac{2}{5}$, $\dfrac{25}{19}$, and $\dfrac{11}{9}$ respectively.
| Test Case Number | $n$ | $m$ | Special Properties | Points per Test Case |
|---|---|---|---|---|
| $1,2$ | $\le 10$ | $\le 10$ | None | $2$ |
| $3,4,5$ | $\le 15$ | $\le 100$ | None | $2$ |
| $6,7,8$ | $\le 100$ | $\le 10^3$ | None | $2$ |
| $9,10$ | $\le 10^3$ | $\le 10^4$ | None | $2$ |
| $11,12$ | $\le 10^4$ | $\le 10^5$ | None | $5$ |
| $13,14$ | $\le 10^5$ | $\le 2\times10^5$ | None | $5$ |
| $15,16$ | $\le 10^5$ | $\le 7\times10^5$ | None | $10$ |
| $17$ | $\le 10$ | $=n-1$ | Directed Tree | $10$ |
| $18$ | $\le 10^3$ | $=n-1$ | Directed Tree | $10$ |
| $19$ | $\le 10^4$ | $=n-1$ | Directed Tree | $10$ |
| $20$ | $\le 10^5$ | $=n-1$ | Directed Tree | $10$ |
The definition of "Directed Tree" is: if the graph is considered as an undirected graph, it forms a tree (as in Sample $1,2$).
All data are guaranteed to be random in a certain way, which means you can safely perform division operations under modulo without worrying about division by zero.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分