Codeforces functionality may be limited from June 18, 19:00 (UTC) to June 19, 3:00 AM (UTC) due to technical maintenance. Polygon will work as usual. ×

G. No Game No Life
time limit per test
2 seconds
memory limit per test
256 megabytes
standard input
standard output

Let's consider the following game of Alice and Bob on a directed acyclic graph. Each vertex may contain an arbitrary number of chips. Alice and Bob make turns alternating. Alice goes first. In one turn player can move exactly one chip along any edge outgoing from the vertex that contains this chip to the end of this edge. The one who cannot make a turn loses. Both players play optimally.

Consider the following process that takes place every second on a given graph with $$$n$$$ vertices:

  1. An integer $$$v$$$ is chosen equiprobably from $$$[1, n + 1]$$$.
  2. If $$$v \leq n$$$, we add a chip to the $$$v$$$-th vertex and go back to step 1.
  3. If $$$v = n + 1$$$, Alice and Bob play the game with the current arrangement of chips and the winner is determined. After that, the process is terminated.

Find the probability that Alice will win the game. It can be shown that the answer can be represented as $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q \not\equiv 0 \pmod{998\,244\,353}$$$. Print the value of $$$P \cdot Q^{-1} \bmod 998\,244\,353$$$.


The first line contains two integers $$$n$$$ and $$$m$$$ — the number of vertices and edges of the graph ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq 10^5$$$).

The following $$$m$$$ lines contain edges description. The $$$i$$$-th of them contains two integers $$$u_i$$$ and $$$v_i$$$ — the beginning and the end vertices of the $$$i$$$-th edge ($$$1 \leq u_i, v_i \leq n$$$). It's guaranteed that the graph is acyclic.


Output a single integer — the probability of Alice victory modulo $$$998\,244\,353$$$.

1 0
2 1
1 2
5 5
1 4
5 2
4 3
1 5
5 4