← 返回题目列表

AtCoder · abc412_g

G. 度和谐

中文机器翻译题面 查看原题

分数: 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