云剪贴板地址：
https://www.luogu.org/paste/uzngt3o6
效果：

题目背景

全球网络（

WWN

）是一个实施“大电信网络”的领导性公司。

WWN

准备在

Borduria

，一个正准备赶走他们的军事独裁者

Kurvi-Tasch

并正在寻求国际公司的投资的国家（完整的关于

Borduria

的描述详见《丁丁历险记》系列）。你的任务是帮助

WWN

决定一个架设网络的方案，使架设的总代价最小。

题目描述

有一些当地的公司正在运行小的网络（下文称为“子网络”），这些子网络部分地覆盖了

n

个

Borduria

最大的城市。

WWN

想要建设能够完全地覆盖这

n

个城市的网络。为了完成这个任务，

WWN

可以选择在两个城市之间建边或者收购一个或多个子网络。你被要求帮助

WWN

设计出一种可以使总代价最小的网络建设方案。

所有的 $n$ 座城市都被定位在一个笛卡尔平面坐标系内。
一共有 $q$ 个子网络可供选择。如果 $q \geq 1$ 那么每个子网络 $c$ （ $1 \leq c \leq q$ ）被定义成一组内联的城市（具体连接方式无关紧要）。
为了连接两个不在同一个子网络内的城市， $WWN$ 需要付出等于这两个城市间欧几里得距离的平方的代价。

你需要决定购买哪些子网络和连接哪些边，以使得总代价最小化。注意子网络的总数目非常小。

输入输出格式

输入格式

输入包含多组数据。

输入文件第一行包含一个正整数，代表测试数据的组数。这一行后有一个空行。每组数据之间也有一个空行。

每组数据的第一行包含两个正整数

n

，

q

。所有的城市都被编号为

1

到

n

。接下来

q

行，每行若干个正整数，描述一个子网络。每个描述开头

2

个正整数，表示该子网络的点的数量和收购价格。该行剩下的所有正整数描述了该子网络里的所有城市。接下来

n

行，每行

2

个正整数，按照

1

到

n

的顺序描述了每个城市的坐标。

输出格式

输出包含

2\times n

行，分别对应每组测试数据。每组输出仅包含一个正整数，表示最小总代价，后接一个空行。

样例输入输出

样例输入

CPP

样例输出

CPP

数据范围与提示

数据范围

1 \leq n \leq 1000\; , \ 0 \leq q \leq 8\; ;

0 \leq \text{每个城市的坐标}\leq 3000 \; , \ \text{每个子网络的收购代价} \leq 2 \times 10^6

提示

每组输出后输出一个空行，包括最后一组数据。

手动翻译（可能有错误）

讨论操作