P14878 [ICPC 2019 Yokohama R] Twin Trees Bros.

为了满足 ICPC（国际可可种植联盟）的需求，你必须检查两棵给定的树是否是双胞胎。 :::align{center}  三维空间中两棵树的示例。 ::: 图论中的术语**树**指的是一个连通图，其中边的数量比节点的数量少 $1$。此外，ICPC 将三维网格点作为树节点的位置。他们对于两棵树是**双胞胎**的定义是：存在一个几何变换函数，能将一棵树的所有节点一一映射到另一棵树的节点上，使得对于一棵树的每条边，另一棵树中都存在一条边连接相应的节点。该几何变换应为以下变换的组合： - 平移：坐标值加上某些常数。 - 具有正比例系数的均匀缩放：所有三个坐标值乘以相同的正常数。 - 围绕 $x$ 轴、$y$ 轴和 $z$ 轴进行任意角度的旋转。 注意，两棵树可能以不止一种方式成为双胞胎，即具有不同的节点对应关系。 编写一个程序，判断两棵树是否是双胞胎，并输出不同节点对应关系的数量。 在下文中，变换将在右手 $xyz$ 坐标系中描述。 样例输入 $1$ 到 $4$ 中的树如下图所示。图中的数字是下面定义的节点编号。 :::align{center}  ::: 对于样例输入 $1$，红色树的每个节点通过以下变换映射到蓝色树的对应节点：平移 $(-3,0,0)$，绕 $z$ 轴旋转 $-\pi/2$，绕 $x$ 轴旋转 $\pi/4$，最后缩放 $\sqrt{2}$ 倍。通过此映射，红色树中位于 $(0,0,0)$、$(1,0,0)$ 和 $(3,0,0)$ 的节点 $\#1$、$\#2$ 和 $\#3$ 分别对应蓝色树中位于 $(0,3,3)$、$(0,2,2)$ 和 $(0,0,0)$ 的节点 $\#6$、$\#5$ 和 $\#4$。这是这对双胞胎树唯一可能的对应关系。 对于样例输入 $2$，红色节点 $\#1$、$\#2$、$\#3$ 和 $\#4$ 可以映射到蓝色节点 $\#6$、$\#5$、$\#7$ 和 $\#8$。还存在另一种节点对应关系，将节点 $\#1$、$\#2$、$\#3$ 和 $\#4$ 映射到 $\#6$、$\#5$、$\#8$ 和 $\#7$。 对于样例输入 $3$，这两棵树**不是**双胞胎。存在将一棵树的节点映射到另一棵树不同节点的变换，但边的连接关系不匹配。 对于样例输入 $4$，不存在将一棵树的节点映射到另一棵树节点的变换。

输入包含单个测试用例，格式如下。 $$ \begin{aligned} &n \\ &x_1\ y_1\ z_1 \\ &\vdots \\ &x_n\ y_n\ z_n \\ &u_1\ v_1 \\ &\vdots \\ &u_{n-1}\ v_{n-1} \\ &x_{n+1}\ y_{n+1}\ z_{n+1} \\ &\vdots \\ &x_{2n}\ y_{2n}\ z_{2n} \\ &u_n\ v_n \\ &\vdots \\ &u_{2n-2}\ v_{2n-2} \end{aligned} $$ 输入描述了两棵树。第一行包含一个整数 $n$，表示每棵树的节点数量（$3 \le n \le 200$）。接下来是两棵树的描述。 一棵树的描述由 $n$ 行给出顶点位置，以及 $n-1$ 行显示顶点的连接关系。 第一棵树的节点编号为 $1$ 到 $n$，第二棵树的节点编号为 $n+1$ 到 $2n$。 三元组 $(x_i, y_i, z_i)$ 给出了编号为 $i$ 的节点的坐标。$x_i$、$y_i$ 和 $z_i$ 是介于 $-1000$ 和 $1000$ 之间（含）的整数。单棵树的节点坐标互不相同。 整数对 $(u_j, v_j)$ 表示编号为 $u_j$ 和 $v_j$ 的节点之间存在一条边（$u_j \ne v_j$）。对于 $1 \le j \le n-1$，满足 $1 \le u_j \le n$ 和 $1 \le v_j \le n$；对于 $n \le j \le 2n-2$，满足 $n+1 \le u_j \le 2n$ 和 $n+1 \le v_j \le 2n$。

如果两棵树是双胞胎，则输出不同节点对应关系的数量。否则，输出 $0$。