1011. 森林

题目描述

设有一个包含 $n$ 个顶点的完全图 $K_n=(V,E)$。

给定 $K_n$ 的 $k$ 个子图：

$G_1=(V,E_1),G_2=(V,E_2),\ldots,G_k=(V,E_k)$，

并满足：

• $G_1,G_2,\ldots,G_k$ 均为无环图；
• $|E_1|=|E_2|=\cdots=|E_k|=m$。

记子图 $G_i$ 中的第 $j$ 条边为 $e_{i,j}$。

定义边集 $S$ 是好的，当且仅当存在 $m$ 个集合 $X_1,X_2,\ldots,X_m$，满足：

• 对于每个 $1\le i\le m$，

  $X_i\subseteq\bigcup_{j=1}^{k}{e_{j,i}}$，且 $1\le |X_i|\le C_i$；

• $S=\displaystyle\bigcup_{i=1}^{m}X_i$；

• 边集 $S$ 所导出的图 $G_S=(V,S)$ 无环。

也就是说，对于每个位置 $i$，可以从 $k$ 个子图的第 $i$ 条边中选择至少 $1$ 条、至多 $C_i$ 条，并要求最终选出的所有边整体仍然构成一个无环图。

请你求出一个好的边集 $S$ 的最大大小。

输入格式

第一行输入一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行输入三个整数 $n,m,k$，分别表示顶点数、每个子图的边数以及子图数量。

第二行输入 $m$ 个整数 $C_1,C_2,\ldots,C_m$。

接下来 $k$ 行，第 $i$ 行输入 $2m$ 个整数：

$u_{i,1},v_{i,1},u_{i,2},v_{i,2},\ldots,u_{i,m},v_{i,m}$，

表示子图 $G_i$ 的 $m$ 条边，其中第 $j$ 条边 $e_{i,j}$ 连接顶点 $u_{i,j}$ 和 $v_{i,j}$。

输出格式

共输出 $T$ 行。

对于每组测试数据，输出一个整数，表示好的边集 $S$ 的最大大小。

数据范围

对于所有测试数据：

• $1\le T\le 100$；
• $1\le n,m,k\le 100$；
• $1\le C_i\le k$；
• $1\le u_{i,j},v_{i,j}\le n$；
• 所有测试数据满足 $\sum n\le 200$，$\sum m\le 200$，$\sum k\le 200$。

题目保证给出的每个子图 $G_i$ 均无环。

样例输入

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

样例输出

1
2

来源：2026“钉耙编程”中国大学生算法设计暑期联赛第 1 场官方题面。