相位

时间限制：$2.0\text{ s}$

空间限制：$128\text{ MiB}$

题目描述

某数据中心中有 $n$ 个用电模块和 $m$ 条抗干扰连接线。第 $i$ 个模块的额定负载为正整数 $w_i$。为了将瞬时功率分散到两路供电相位，每个模块必须选择相位 $0$ 或相位 $1$。

某些模块之间存在直接的同步连线。若连线两端接入相同相位，会在切换时产生不可接受的峰值，因此每条连接线的两个端点必须选择不同相位。保证给出的连接关系至少存在一种满足要求的分配。

对一种合法分配，把所有接入相位 $1$ 的模块负载相加，得到这种分配在第二路供电上的总负载，称为它的相位负载。管理人员并不关心有多少种具体分配，而是关心系统可能呈现出多少个不同的总负载值。

求全部合法相位分配一共能产生多少种不同的相位负载。若多种分配得到相同数值，该数值只计算一次。

输入格式

第一行两个整数 $n,m$，表示模块数和连接线数。

第二行 $n$ 个正整数 $w_1,w_2,\ldots,w_n$，表示每个模块的负载。

接下来 $m$ 行，每行两个整数 $u,v$，表示模块 $u$ 与模块 $v$ 之间有一条连接线。

输出格式

输出一行一个整数，表示不同相位负载的数量。

输入样例 1

4 2
1 2 3 4
1 2
3 4

输出样例 1

3

输入样例 2

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

输出样例 2

4

输入样例 3

见附件 sample/phase3.in

输出样例 3

见附件 sample/phase3.out

数据范围

对于所有测试点，保证：

• $1\le n\le 30000$，$0\le m\le 10^5$；
• $1\le w_i$，且 $\sum_{i=1}^n w_i\le 30000$；
• 图中没有自环和重边；
• 给出的图是二分图。

每个测试点单独计分。