为了满足 ICPC（国际可可种植园联盟）的需求，你需要检查给定的两棵树是否为“孪生树”。

三维空间中两棵树的示例。

图论中的“树”是指一个连通图，其边数比节点数少 1。此外，ICPC 还给出了树节点在三维网格中的位置。两棵树被称为“孪生树”的定义是：存在一个几何变换函数，它能将一棵树的所有节点一一映射到另一棵树的节点上，使得第一棵树的每一条边在另一棵树中都有对应的边连接相应的节点。该几何变换应为以下变换的组合：

• 平移：在坐标值上加上某些常数。
• 均匀缩放：乘以正的缩放因子，即将所有三个坐标值乘以同一个正的常数。
• 旋转：绕 $x$ 轴、$y$ 轴或 $z$ 轴旋转任意角度。

注意，两棵树可能以不止一种方式成为孪生树，即存在不同的节点对应关系。

编写一个程序，判断两棵树是否为孪生树，并输出不同节点对应关系的个数。

输入格式

输入描述了两棵树。第一行包含一个整数 $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 \neq 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。

样例

样例输入 1

3
0 0 0
1 0 0
3 0 0
1 2
2 3
0 0 0
0 2 2
0 3 3
4 5
5 6

样例输出 1

1

样例输入 2

4
1 0 0
2 0 0
2 1 0
2 -1 0
1 2
2 3
2 4
0 1 1
0 0 0
0 2 0
0 0 2
5 6
5 7
5 8

样例输出 2

2

说明

样例输入 1 到 4 中的树如下图所示。图中的数字是下文定义的节点编号。

Sample Input 1

Sample Input 2

Sample Input 3

Sample Input 4

以下变换均在右手 $xyz$ 坐标系中描述。

对于样例输入 1，红色树的每个节点通过以下变换映射到蓝色树的对应节点：平移 $(-3, 0, 0)$，绕 $z$ 轴旋转 $\pi/2$，绕 $x$ 轴旋转 $\pi/4$，最后缩放 $2\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，不存在将一棵树的节点映射到另一棵树的节点的变换。