Twin Trees Bros.

To meet the demand of ICPC (International Cacao Plantation Consortium), you have to check whether two given trees are twins.

Example of two trees in the three-dimensional space.

In graph theory, a tree is a connected graph whose number of edges is one less than its number of nodes. ICPC also gives each tree node as a point on a three-dimensional grid. Two trees are twins if there is a geometric transformation function that maps the nodes of one tree one-to-one onto the nodes of the other, such that for each edge of one tree, there is an edge in the other tree connecting the corresponding nodes. The transformation must be a combination of the following:

• translations, which add constants to the coordinate values,
• uniform scaling with positive scale factors, which multiply all three coordinate values by the same positive constant, and
• rotations by any amount around the x-, y-, or z-axis.

Two trees can be twins in more than one way, with different node correspondences.

Write a program that decides whether two trees are twins and outputs the number of different node correspondences.

Transformations are described in the right-handed xyz-coordinate system.

The trees in sample inputs 1 through 4 are shown in the following figures. The numbers in the figures are the node numbers defined below.

For sample input 1, each node of the red tree maps to the corresponding node of the blue tree by a transformation that translates by (-3, 0, 0), rotates by $-\pi/2$ around the z-axis, rotates by $\pi/4$ around the x-axis, and finally scales by $\sqrt{2}$. Under this mapping, nodes 1, 2, and 3 of the red tree, at (0, 0, 0), (1, 0, 0), and (3, 0, 0), correspond to nodes 6, 5, and 4 of the blue tree, at (0, 3, 3), (0, 2, 2), and (0, 0, 0). This is the only possible correspondence of the twin trees.

For sample input 2, red nodes 1, 2, 3, and 4 can map to blue nodes 6, 5, 7, and 8. Another correspondence maps nodes 1, 2, 3, and 4 to 6, 5, 8, and 7.

For sample input 3, the two trees are not twins. Some transformations map the nodes of one tree to distinct nodes of the other, but the edge connections do not agree.

For sample input 4, no transformation maps the nodes of one tree to those of the other.

The first line contains $n$, the number of nodes in each tree, where $3 \le n \le 200$. Descriptions of two trees follow. A description consists of $n$ lines giving the vertex positions and $n-1$ lines giving the edges. The first tree has nodes numbered 1 through $n$, and the second tree has nodes numbered $n+1$ through $2n$.

The input has the following format.

n
x1 y1 z1
.
.
.
xn yn zn
u1 v1
.
.
.
un−1 vn−1
xn+1 yn+1 zn+1
.
.
.
x2n y2n z2n
un vn
.
.
.
u2n−2 v2n−2

Each coordinate $x_i$, $y_i$, and $z_i$ is an integer from $-1000$ to $1000$. Nodes within a single tree have distinct coordinates.

The pair $(u_j, v_j)$ means an edge exists between nodes $u_j$ and $v_j$, where $u_j \ne v_j$. For the first tree, $1 \le u_j, v_j \le n$. For the second tree, $n+1 \le u_j, v_j \le 2n$.

If the two trees are twins, output the number of different node correspondences. Otherwise, output 0.