问题文的变更点

• $K$ 不再固定，而是对于每棵树给定 $K_i$，每棵树有2到100个节点。
• 修改了 $c_i$ 的生成方式。中间节点的比例下降，弱节点增加，$c_i$ 的值总体减少。

问题文

在二维坐标平面上有 $N$ 个顶点，分别是顶点 $1, \ldots, N$。此外，还给出了 $S$ 个无向树 $T_1, \ldots, T_S$。

你的任务是在平面上连接一些顶点以形成一个包含 $N$ 个顶点的无向图 $G$，然后从 $G$ 中“提取”出 $S$ 个图。提取出的图与 $T_1, \ldots, T_S$ 越相似，得分就越高。下面对每个事项进行详细说明。

• 关于平面上的顶点：顶点 $i$ $(1 \leq i \leq N)$ 的坐标是 $(x_i, y_i)$，这些坐标都是介于 $0$ 到 $1000$ 之间的整数。此外，每个顶点都有一个正整数值，称为 权值，顶点 $i$ 的权值是 $c_i$。

• 关于树 $T_1, \ldots, T_S$：每棵树都有 $K_i$ 个编号为 $1, \ldots, K$ 的顶点。为方便起见，这些树被输入为以编号 $1$ 的顶点为根的有根树。对于树 $T_i$ $(1 \leq i \leq S)$ 中编号为 $j$ $(2 \leq j \leq K_i)$ 的顶点，其父亲是编号为 $p_{i,j}$ 的顶点。

• 关于添加边：可以在图 $G$ 中添加 $0$ 条或多条无向边，总数不超过 $100000$ 条。但是，要添加边 $\\{i, j\\}$ $(i \neq j)$，顶点 $i$ 和 $j$ 之间的欧几里得距离必须小于等于 $c_i + c_j$。此外，不能产生自环或重边。

• 关于提取图：对于每棵树 $T_i$ $(1 \leq i \leq S)$，请指定 $G$ 中的 $K_i$ 个不同顶点 $V_{i,1}, \ldots, V_{i,K_i}$。这表示对于每个 $j$ $(1 \leq j \leq K_i)$，将顶点 $V_{i,j}$ 对应到树 $T_i$ 的编号为 $j$ 的顶点。同一个顶点可以与多棵树相关联。

• 关于得分：对于每棵树 $T_i$ $(1 \leq i \leq S)$，计算如下得分，然后将所有树的得分相加作为你的得分。

• 若存在整数 $x, y$ $(1 \leq x, y \leq K_i)$，$T_i$ 有边 $\\{x, y\\}$，但 $G$ 没有边 $\\{V_{i,x}, V_{i,y}\\}$：得 $0$ 分

• 否则，设形如 $(x, y)$ $(1 \leq x, y \leq K_i)$ 的整数对有 $G$ 有边 $\\{V_{i,x}, V_{i,y}\\}$，但 $T_i$ 没有边 $\\{x, y\\}$ 的个数为 $e_i$。

  • 当 $e_i = 0$ 时：得 $100$ 分
  • 当 $e_i = 1$ 时：得 $10$ 分
  • 当 $e_i = 2$ 时：得 $1$ 分
  • 当 $e_i \geq 3$ 时：得 $0$ 分

约束条件

• $N = 1000$
• $S = 1000$
• $2 \leq K_i \leq 100$
• $0 \leq x_i, y_i \leq 1000$
• $1 \leq c_i \leq 1500$
• $1 \leq p_{i,j} \leq j-1$
• 输入中的所有值都是整数。

输入

输入从标准输入读入，具有以下格式：

$N$ $S$ $x_1$ $y_1$ $c_1$ $x_2$ $y_2$ $c_2$ $:$ $x_N$ $y_N$ $c_N$ $K_1$ $p_{1,2}$ $p_{1,3}$ $\\ldots$ $p_{1,K_1}$ $K_2$ $p_{2,2}$ $p_{2,3}$ $\\ldots$ $p_{2,K_2}$ $:$ $K_S