CF2176D.Fibonacci Paths

You are given a directed graph consisting of $n$ vertices and $m$ edges. Each vertex $v$ corresponds to a positive number $a_v$. Count the number of distinct simple paths$^{\text{∗}}$ consisting of at least two vertices, such that the sequence of numbers written at the vertices along the path forms a generalized Fibonacci sequence.

In this problem, we will consider that the sequence of numbers $x_0, x_1, \ldots, x_k$ forms a generalized Fibonacci sequence if:

• $x_0, x_1$ are arbitrary natural numbers.
• $x_i = x_{i - 2} + x_{i - 1}$ for all $2 \le i \le k$.

Note that a generalized Fibonacci sequence consists of at least two numbers.

Since the answer may be large, output it modulo $998\,244\,353$.

$^{\text{∗}}$A simple path in a directed graph is a sequence of vertices $v_1, v_2, \ldots, v_k$ such that each vertex in the graph appears in the path at most once and there is a directed edge from $v_i$ to $v_{i+1}$ for all $i \lt k$.

你被给定一个由 $n$ 个顶点和 $m$ 条有向边构成的有向图。每个顶点 $v$ 对应一个正整数 $a_v$。请统计满足以下条件的不同简单路径$^{\text{∗}}$ 的数量：该路径至少包含两个顶点，且路径上各顶点对应的数字序列构成一个广义斐波那契序列。

在本题中，我们称一个数字序列 $x_0, x_1, \ldots, x_k$ 构成广义斐波那契序列，当且仅当：

• $x_0, x_1$ 是任意正整数；
• 对所有 $2 \le i \le k$，均有 $x_i = x_{i - 2} + x_{i - 1}$。

注意：广义斐波那契序列至少包含两个数。

由于答案可能很大，请将结果对 $998\,244\,353$ 取模后输出。

$^{\text{∗}}$ 有向图中的一条简单路径是指一个顶点序列 $v_1, v_2, \ldots, v_k$，使得图中每个顶点在该路径中至多出现一次，且对所有 $i < k$，均存在一条从 $v_i$ 指向 $v_{i+1}$ 的有向边。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two numbers $n$, $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$) — the number of vertices and the number of edges in the graph, respectively.

The second line of each test case contains $n$ natural numbers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{18}$) — the numbers written at the vertices.

The next $m$ lines contain the edges of the graph; each edge is defined by two natural numbers $v, u$ ($1 \le v, u \le n$, $u \neq v$), denoting a directed edge from $v$ to $u$. It is guaranteed that there are no multiple edges in the graph.

It is guaranteed that the sum of $n$ and the sum of $m$ across all test cases do not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$、$m$（$2 \le n \le 2 \cdot 10^5$，$1 \le m \le 2 \cdot 10^5$）——分别表示图中顶点数和边数。

每个测试用例的第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^{18}$）——表示写在各顶点上的数值。

接下来的 $m$ 行描述图中的边；每条边由两个正整数 $v$、$u$（$1 \le v, u \le n$，$u \neq v$）定义，表示一条从顶点 $v$ 指向顶点 $u$ 的有向边。保证图中不存在重边。

保证所有测试用例的 $n$ 之和与 $m$ 之和均不超过 $2 \cdot 10^5$。

For each test case, output the number of paths that form a generalized Fibonacci sequence, modulo $998\,244\,353$.

对于每个测试用例，输出构成广义斐波那契数列的路径数量，对 $998\,244\,353$ 取模。

Explanation of the first test case example (the vertex number is outside the brackets, the number written in the vertex is inside):

In this case, there are 5 generalized Fibonacci paths: ($1, 2$), ($1, 3$), ($2, 4$), ($3, 4$), ($1,3,4$). For example, for the path ($1,3,4$), the sequence of numbers written at the vertices along this path is: [$3,3,6$]. As can be easily seen, the third number in the sequence is the sum of the two previous ones.

Explanation of the second test case example:

In this case, there are 9 generalized Fibonacci paths: ($1, 2$), ($1, 4$), ($2, 3$), ($2, 4$), ($3, 1$), ($3, 4$), ($1, 2, 4$), ($2, 3, 4$), ($3, 1, 4$). Note that for the path ($1, 2, 3$), the sequence of numbers written at the vertices along this path is: [$1,1,1$], and it is not a generalized Fibonacci sequence.

第一个测试用例示例的说明（括号外为顶点编号，括号内为顶点上所写的数字）：

本例中存在 5 条广义斐波那契路径：($1, 2$)、($1, 3$)、($2, 4$)、($3, 4$)、($1,3,4$)。例如，对于路径 ($1,3,4$)，沿该路径各顶点上所写数字构成的序列为：[$3,3,6$]。显然，该序列中第三个数等于前两个数之和。

第二个测试用例示例的说明：

本例中存在 9 条广义斐波那契路径：($1, 2$)、($1, 4$)、($2, 3$)、($2, 4$)、($3, 1$)、($3, 4$)、($1, 2, 4$)、($2, 3, 4$)、($3, 1, 4$)。注意，对于路径 ($1, 2, 3$)，沿该路径各顶点上所写数字构成的序列为：[$1,1,1$]，它不构成广义斐波那契序列。