[AdditionalFile6496.zip](file://AdditionalFile6496.zip?type=additional_file)

#6496. 「雅礼集训 2018 Day1」仙人掌

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

给出一张 $n$ 个点 $m$ 条边的无向连通图，其中每条边至多属于一个简单环，保证没有自环，可能有重边。你需要为其中每条边定向，其中第 $i$ 个点的出度不能超过 $a_i$，求方案数。

输入格式

第一行包括两个正整数 $n, m$。

接下来 $m$ 行，每行两个正整数，表示有一条边连接这两个点。

最后一行 $n$ 个正整数，其中第 $i$ 个表示 $a_i$。

输出格式

输出一个非负整数，表示答案对 $998244353$ 取模后的结果。

样例

输入

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

输出

7

数据范围与提示

对于全部数据，$1 \leq a_i \leq n \leq 10^5, 1 \leq m \leq 2×10^5$。

• 子任务 $\rm 1(points:10)$：$m \leq 20$
• 子任务 $\rm 2(points:10)$：$m= n - 1$且 $a_i = 2$
• 子任务 $\rm 3(points:20)$：$a_i = 2$
• 子任务 $\rm 4(points:20)$：$m = n - 1$
• 子任务 $\rm 5(points:20)$：每个点至多属于一个简单环
• 子任务 $\rm 6(points:20)$：无特殊限制