Background

zbw is wandering in City B.

Problem Description

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$.

Input Format

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 Format

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

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

Hint

Sample explanation: the answers for the samples are $\dfrac{2}{5}$, $\dfrac{25}{19}$, and $\dfrac{11}{9}$.

Constraints

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