CF1411G.No Game No Life

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

我们考虑 Alice 和 Bob 在一个有向无环图（DAG）上进行的如下游戏：每个顶点可以包含任意数量的筹码。Alice 和 Bob 轮流行动，Alice 先手。在一轮中，玩家必须恰好将一枚位于某顶点上的筹码，沿着从该顶点出发的一条有向边移动到该边的终点。无法行动者判负。双方均采取最优策略。

考虑如下过程，该过程在给定的含 $n$ 个顶点的图上每秒执行一次：

1. 从区间 $[1, n + 1]$ 中等概率地随机选取一个整数 $v$；
2. 若 $v \leq n$，则向第 $v$ 个顶点添加一枚筹码，并返回步骤 1；
3. 若 $v = n + 1$，则 Alice 和 Bob 以当前筹码分布为初始状态进行上述游戏，并确定获胜方；此后该过程终止。

求 Alice 获胜的概率。可以证明该概率可表示为 $\frac{P}{Q}$，其中 $P$ 与 $Q$ 互质，且 $Q \not\equiv 0 \pmod{998\,244\,353}$。请输出 $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.

第一行包含两个整数 $n$ 和 $m$ —— 分别表示图的顶点数和边数（$1 \leq n \leq 10^5$，$0 \leq m \leq 10^5$）。

接下来的 $m$ 行描述各条边。其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ —— 表示第 $i$ 条边的起点和终点顶点（$1 \leq u_i, v_i \leq n$）。保证该图是无环的。

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

输出一个整数——Alice 获胜的概率对 $998\,244\,353$ 取模的结果。