G - Degree Harmony Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 650 点

問題文

頂点に 1 から N の番号がついた N 頂点 M 辺の単純無向グラフ G が与えられます。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 が成り立つ。

良いグラフが存在するか判定してください。存在する場合は、良いグラフとしてあり得るグラフのうち辺数が最小のものの辺数を出力してください。

制約

  • 1 \leq N \leq 150
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq u_i \lt 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

辺集合が 2 番目の辺のみで構成された全域部分グラフは良いグラフです。

入力例 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

Score : 650 points

Problem Statement

You are given a simple undirected graph G with N vertices and M edges, where vertices are numbered from 1 to N. The i-th edge connects vertices u_i and v_i.
A spanning subgraph G' of G that satisfies the following condition is called a good graph:

  • For all integers i satisfying 1 \leq i \leq N, the following condition holds:
    • Let d_i be the degree of vertex i in G'. Then, d_i \leq A_i and d_i \bmod 2 = A_i \bmod 2 hold.

Determine whether a good graph exists. If it exists, output the minimum number of edges among all possible good graphs.

Constraints

  • 1 \leq N \leq 150
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq u_i < v_i \leq N
  • The given graph is simple.
  • 1 \leq A_i \leq 150
  • 1 \leq \sum_{i=1}^N A_i \leq 150
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

If no good graph exists, output -1. If it exists, output the minimum number of edges among all possible good graphs.

Sample Input 1

3 3
1 2 3
1 2
1 3
2 3

Sample Output 1

1

The spanning subgraph whose edge set consists of only the 2nd edge is a good graph.

Sample Input 2

4 3
1 1 1 1
1 3
2 3
3 4

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

3