分数: 650 点
问题陈述
给你一个简单的无向图 G 与 N 顶点和 M 边,其中顶点编号为 1 to N。的 i第一条边连接顶点 u_i 和 v_i.
跨越子图
满足以下条件的 G' of G 称为 好图:
- 对于所有整数 i 满意 1 \leq i \leq N,以下条件成立:
- 让 d_i 是顶点的度数 i in G'。然后, d_i \leq A_i 和 d_i \bmod 2 = A_i \bmod 2 按住。
确定是否存在好的图表。如果存在,则输出所有可能的好图中的最小边数。
约束
- 1 \leq N \leq 150
- 0 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq u_i < v_i \leq N
- 给定的图表很简单。
- 1 \leq A_i \leq 150
- 1 \leq \sum_{i=1}^N A_i \leq 150
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \dots A_N u_1 v_1 u_2 v_2 \vdots u_M v_M
输出
如果不存在好的图,则输出 -1。如果存在,则输出所有可能的好图中的最小边数。
示例输入 1
3 3 1 2 3 1 2 1 3 2 3
示例输出 1
1
生成子图,其边集仅由 2nd 边是一个很好的图。
示例输入 2
4 3 1 1 1 1 1 3 2 3 3 4
示例输出 2
-1
示例输入 3
5 6 3 1 4 3 1 1 2 1 3 1 4 2 3 3 4 3 5
示例输出 3
3