AT_abc412_g.[ABC412G] Degree Harmony

给定一个有 $N$ 个顶点、$M$ 条边的简单无向图 $G$，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。
对于 $G$ 的一个全域子图 $G'$，若满足以下条件，则称其为好图：

• 对于所有满足 $1 \leq i \leq N$ 的整数 $i$，都有：
  • 设 $d_i$ 为 $G'$ 中顶点 $i$ 的度数，则 $d_i \leq A_i$ 且 $d_i \bmod 2 = A_i \bmod 2$。

请判断是否存在好图。如果存在，请输出作为好图的所有可能图中边数最少的那个的边数。

输入以如下格式从标准输入读入。

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

如果不存在好图，输出 -1。如果存在，输出作为好图的所有可能图中边数最少的那个的边数。

限制条件

• $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$
• 输入的所有值均为整数

样例解释 1

仅由第 $2$ 条边构成的全域子图是好图。

由 ChatGPT 4.1 翻译