#P17262. [2025年南开中学集训]橘猫森林

[2025年南开中学集训]橘猫森林

题目描述

茂密的森林中,小路交错纵横,一共有 nn 个岔路口,第 ii 个岔路口有美丽度 aia_i,这些岔路口由 mm 条可以双向通行的道路所连接,第 ii 条道路连接岔路口 uiu_i 和 viv_i,不存在两条或多条道路连接相同的两个岔路口。

接下来 nn 天,由于雨季的来临,这些岔路口会不断的被积水所淹没,一个岔路口如果被积水淹没,那么这个路口以及与其相连接的路都不能通行,第 ii 天被淹没的岔路口的编号为 pip_i。

由于不能通行的道路的存在,森林被分成了若干个连通块,橘猫们对于连通块的美丽度有独特的见解:

  • 若连通块的形态是一棵树,其美丽度为块内所有岔路口的美丽度之和。
  • 若连通块的形态不是树,其美丽度为 11。

在任意一天,整个森林的美丽度是所有连通块的美丽度的乘积。

整个雨季的美丽度是从第 00 天(没有任何一个岔路口被淹没)到第 n−1n-1 天森林的美丽度之和。

橘猫们盼望着在雨季看到美景,请你帮她们求出对于所有可能的排列 p1∼np_{1 \sim n},对应的雨季的美丽度之和是多少?

由于森林可能会非常美丽,你只需要输出美丽度  mod 998244353\bmod 998244353 的值即可。

输入格式

第一行两个整数 nn 和 mm,表示岔路口的数量和道路的数量。

第二行 nn 个整数,表示每个岔路口的美丽度。

第 3∼m+23 \sim m+2 行,每行两个整数 uiu_i 和 viv_i,表示第 ii 条道路两端的岔路口编号。

输出格式

输出一行一个整数,表示所有可能的排列所对应雨季的美丽度之和。

输入输出样例

输入 #1

3 3
1 2 3
1 2
2 3
3 1

输出 #1

42

输入 #2

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

输出 #2

290

说明/提示

样例 #1

该组样例满足子任务 1 的限制。

样例 #2

该组样例满足子任务 1 的限制。

样例 #3

见下发的 ex_forest3.in/.out。

该组样例满足子任务 1 的限制。

样例 #4

见下发的 ex_forest4.in/.out。

该组样例满足子任务 2 的限制。

样例 #5

见下发的 ex_forest5.in/.out。

该组样例满足子任务 3 的限制。

样例 #6

见下发的 ex_forest6.in/.out。

该组样例满足子任务 4 的限制。

样例 #7

见下发的 ex_forest7.in/.out。

该组样例满足子任务 5 的限制。

数据范围

对于所有测试数据,满足 1≤n≤231 \leq n \leq 23,0≤m≤n(n−1)20 \leq m \leq \frac {n(n-1)}{2},0≤ai<9982443530 \leq a_i < 998244353,ui≠viu_i \not= v_i。

子任务编号 分值 限制 特殊性质
11 2020 n≤9n \le 9 无
22 1010 无 A\text{A}
33 1515 n≤17n \leq 17 无
44 n≤20n \leq 20
55 4040 无

特殊性质 A\text{A}:最初的图是一个森林。