P13949 [EC Final 2019] Travel

“我已经厌倦了世界上相同的风景。”——$\textit{Philosopher Pang}$ $\textit{Pang}$ 的世界可以简化为一个有向图 $G$，包含 $n$ 个顶点和 $m$ 条边。 在 $G$ 中，一条 $\textit{路径}$ 是一个有序顶点序列 $(v_0,\ldots,v_{t-1})$，其中 $t$ 是某个非负整数，满足对于所有 $0\le i

第一行包含 $3$ 个整数 $n$、$m$ 和 $k$（$1\le n\le 2000, 0\le m\le 4000, 0\le k\le 1000000000$）。 接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示一条从顶点 $a$ 到顶点 $b$ 的有向边（$1\le a, b\le n, a\neq b$）。 没有两条边连接同一对顶点且方向相同。

输出一个整数，表示满足条件的有序对 $(P_1,P_2)$ 的数量，对 $998244353$ 取模。

由 ChatGPT 4.1 翻译