No Game No Life

题意翻译

### 题目描述 Alice 和 Bob 在玩游戏。 在他们面前有一张 $n$ 个点，$m$ 条边的有向无环图，每个点有若干芯片，数量为 $a_i$。Alice 和 Bob 轮流操作，Alice 先手。定义玩家的一次操作为将图上的某一顶点的一个芯片根据有向边移到另外一个顶点上。每人每次只能操作一次。如果一个人不能操作，那么他输掉游戏。 在游戏开始后，每一秒在图上都会发生如下的操作： 1. 在 $[1,n+1]$ 范围内等概率选取一个整数 $v$。 2. 如果 $v \leq n$，那么在 $v$ 顶点放置一个芯片，这一秒操作结束。 3. 如果 $v = n + 1$，那么 Alice 和 Bob 开始游戏，游戏结束后所有操作停止。 保证 Alice 和 Bob 都绝对聪明。 现在请你求出 Alice 赢的概率。对 $998244353$ 取模。 即若概率为最简分数 $\dfrac{p}{q}$（保证 $q \not \equiv 0 \bmod 998244353$），你只需要输出 $x$ 使得 $qx \equiv p \bmod 998244353$，可以证明这样的 $x$ 是唯一的。 ### 输入格式 第一行两个整数 $n,m$，表示有向无环图的顶点个数与边数。 接下来 $m$ 行，每行两个数 $u,v$，表示从 $u$ 到 $v$ 有一条有向边。 ### 输出格式 仅一行，表示 Alice 赢的概率。对 $998244353$ 取模。 ### 数据范围 $1 \leq n \leq 10^5,1 \leq m \leq 10^5$。

题目描述

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

1 0

输出样例 #1

0

输入样例 #2

2 1
1 2

输出样例 #2

332748118

输入样例 #3

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

输出样例 #3

931694730