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 翻译