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

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

输入格式

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

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

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

输出格式

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

样例

样例输入 1

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

样例输出 1

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) :无特殊限制