P6154 Random Walk

zbw is wandering in City B.

City B can be seen as a **directed acyclic graph** with $n$ vertices and $m$ edges. **Multiple edges may exist**. zbw walks randomly in City B. He will randomly choose one path among all paths, and every path is chosen with equal probability. The starting vertex and the ending vertex of a path may be the same. Define the length of a path as the number of edges it passes through. You need to compute the expected length of the path zbw walks, and output the answer modulo $998244353$.

The first line contains two integers $n, m$. The next $m$ lines each contain two integers $x, y$, indicating that there is a directed edge from $x$ to $y$.

Output one integer per line, representing the answer modulo $998244353$.

Sample explanation: the answers for the samples are $\dfrac{2}{5}$, $\dfrac{25}{19}$, and $\dfrac{11}{9}$. ## Constraints | Test Point ID | $n$ | $m$ | Special Property | Score per Test Point | | :----------: | :----------: | :----------: | :----------: | :----------: | | $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\times 10^5$ | None | $5$ | | $15,16$ | $\le 10^5$ | $\le 7\times 10^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$ | Here, a “Directed Tree” means: if you view the graph as an undirected graph, it is a tree (as in samples $1,2$). It is guaranteed that all testdata is generated randomly in some way. This means you may assume that during the algorithm, you can safely perform division modulo $998244353$ without worrying about dividing by zero. Translated by ChatGPT 5