UVA1151 买还是建 Buy or Build

万维网（WWN）是一家运营大型电信网络的领先公司。 WWN 希望在 Borduria 建立一个新的网络，您需要帮助 WWN 确定如何以最低的总成本设置其网络。有几个本地公司运营着一些小型网络（以下称为子网），部分覆盖了 Borduria 的 $n$ 个最大城市。WWN 希望建立一个连接所有 $n$ 个城市的网络。要实现这一目标，它可以从头开始在城市之间建设网络，也可以从本地公司购买一个或多个子网。您需要帮助 WWN 决定如何以最低的总成本建设其网络。 1. 所有 $n$ 个城市都给出其二维坐标。 2. 存在 $q$ 个子网。 如果 $q \ge 1$,给出每个子网中连接的城市。（不用关心连接的形状） 3. 每个子网只能购买，不能被分割。 4. 连接两个不相通的城市，必须建立一个边，其建设成本是城市之间欧几里德距离的平方。 您的任务是决定购买哪些现有网络以及建设哪些边，使得总成本最低。

输入文件的第一行是一个整数 $T$，表示测试数据的组数。接下来是一个空白行。每两组测试数据之间也有一个空白行。 对于每组测试数据： 第一行是两个整数，分别是城市的总数 $n$ 和子网的数量 $q$，$1 \le n \le 1000$，$0 \le q \le 8$。城市的编号从 1 到 $n$。 接下来 $q$ 行，每行多个整数，第一个整数表示这个子网中的城市的数量 $m$，第二个整数表示购买这个子网的费用（费用不超过 $2 \times 10^6$），剩下的 $m$ 个整数表示这个子网包含的城市。 接下来 $n$ 行，每行两个整数，表示第 $i$ 个城市的坐标。（坐标的数字范围是 0 到 3000）

对于每组测试数据输出一行，输出建设网络的总费用。每组输出之间用一个空行隔开。 Translated by @kevensice__。