Edge Reorientation for Acyclic Graphs

You are given a directed graph with \(n\) vertices and \(m\) edges. The graph has no multiple edges, no self‐loops, and for any pair of vertices there is never a 2‐cycle (i.e. if there is an edge from \(u\) to \(v\) then there is no edge from \(v\) to \(u\)).

You are allowed to change (flip) the direction of some edges. After flipping, the final orientation of each edge is determined as follows: for an edge originally directed from \(u\) to \(v\), if in the final acyclic orientation vertex \(u\) comes before \(v\) then no flip is performed; otherwise, if \(v\) comes before \(u\) then the edge is flipped. In other words, a valid flipping plan is one in which, after applying the flips, the resulting directed graph is acyclic.

For each valid flipping plan (where the plan is defined by the set of edges whose directions are changed) let its cost be the number of edges flipped. Your task is to compute the sum of the costs over all valid flipping plans, and output the answer modulo \(998244353\).

Hint: Any acyclic orientation of the graph can be produced by taking a permutation (a linear ordering) of the \(n\) vertices and, for every edge, orienting it from the vertex that appears earlier to the vertex that appears later. Since the input gives the original orientation, in the flipping plan the cost incurred by an edge is \(0\) if its orientation agrees with the ordering and \(1\) otherwise.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of vertices and edges respectively.

Each of the following \(m\) lines contains two integers \(u\) and \(v\) (1-indexed) indicating a directed edge from \(u\) to \(v\> in the original graph.

outputFormat

Output a single integer, which is the sum of the number of flipped edges over all valid flipping plans (i.e. all acyclic orientations reachable by flipping some edges) taken modulo \(998244353\).

sample

3 3
1 2
2 3
3 1

3