G - Degree Harmony 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 650 点

問題文

頂点に 1 から N の番号がついた N 頂点 M 辺の単純無向グラフ G が与えられます。i 番目の辺は頂点 u_i と頂点 v_i を結ぶ辺です。
また、正整数列 A = (A_1, A_2, \dots, A_N) が与えられます。
G の全域部分グラフ G' であって次の条件を満たすものを 良いグラフ と呼びます。

  • 1 \leq i \leq N を満たす整数 i 全てについて、G' における頂点 i の次数は A_i 以下である。

良いグラフの辺数としてあり得る最大値を求めてください。

T 個のテストケースが与えられるので、それぞれについて問題を解いてください。

制約

  • 1 \leq T \leq 10
  • 2 \leq N \leq 500
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i \leq N-1
  • \displaystyle \sum_{i=1}^N A_i \leq 500
  • 1 \leq u_i \lt v_i \leq N
  • i \neq j ならば (u_i, v_i) \neq (u_j, v_j)
  • 全てのテストケースにおける \displaystyle \left(\sum_{i=1}^N A_i\right)^3 の総和は 500^3 以下
  • 全てのテストケースにおける M の総和は 2\times 10^5 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケース \mathrm{case}_t は以下の形式で与えられる。

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

出力

T 行出力せよ。i 行目には、i 番目のテストケースについて良いグラフの辺数としてあり得る最大値を出力せよ。

入力例 1

3
4 4
2 2 1 1
1 2
1 3
1 4
2 3
6 7
3 3 1 1 1 1
1 2
1 3
1 5
2 3
2 5
3 4
5 6
10 12
1 2 2 1 1 1 1 1 1 1
1 2
1 5
1 8
2 3
2 4
3 4
5 6
5 7
6 7
8 9
8 10
9 10

出力例 1

3
3
5

1 番目のテストケースについて、辺集合が 1,3,4 番目の辺のみで構成された全域部分グラフは良いグラフです。4 本以上辺を含む良いグラフは構成できないため、答えは 3 です。

Score : 650 points

Problem Statement

You are given a simple undirected graph G with N vertices numbered 1 to N and M edges. The i-th edge connects vertices u_i and v_i.
You are also given a sequence of positive integers A = (A_1, A_2, \dots, A_N).
A spanning subgraph G' of G is called a good graph if it satisfies the following condition.

  • For every integer i with 1 \leq i \leq N, the degree of vertex i in G' is at most A_i.

Find the maximum possible number of edges in a good graph.

You are given T test cases; solve each of them.

Constraints

  • 1 \leq T \leq 10
  • 2 \leq N \leq 500
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i \leq N-1
  • \displaystyle \sum_{i=1}^N A_i \leq 500
  • 1 \leq u_i \lt v_i \leq N
  • (u_i, v_i) \neq (u_j, v_j) if i \neq j.
  • The sum of \displaystyle \left(\sum_{i=1}^N A_i\right)^3 over all test cases is at most 500^3.
  • The sum of M over all test cases is at most 2\times 10^5.
  • All input values are integers.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case \mathrm{case}_t is given 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

Print T lines. The i-th line should contain the maximum possible number of edges in a good graph for the i-th test case.

Sample Input 1

3
4 4
2 2 1 1
1 2
1 3
1 4
2 3
6 7
3 3 1 1 1 1
1 2
1 3
1 5
2 3
2 5
3 4
5 6
10 12
1 2 2 1 1 1 1 1 1 1
1 2
1 5
1 8
2 3
2 4
3 4
5 6
5 7
6 7
8 9
8 10
9 10

Sample Output 1

3
3
5

For the 1-st test case, the spanning subgraph whose edge set consists of only the 1-st, 3-rd, and 4-th edges is a good graph. No good graph with 4 or more edges can be constructed, so the answer is 3.