Problem: Twin Trees Bros.

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

<image>
Example of two trees in the three-dimensional space.

The term tree in the graph theory means a connected graph where the number of edges is one less than the number of nodes. ICPC, in addition, gives three-dimensional grid points as the locations of the tree nodes. Their definition of two trees being twins is that, there exists a geometric transformation function which gives a one-to-one mapping of all the nodes of one tree to the nodes of the other such that for each edge of one tree, there exists an edge in the other tree connecting the corresponding nodes. The geometric transformation should be a combination of the following transformations:

* translations, in which coordinate values are added with some constants,
* uniform scaling with positive scale factors, in which all three coordinate values are multiplied by the same positive constant, and
* rotations of any amounts around either $x$-, $y$-, and $z$-axes.



Note that two trees can be twins in more than one way, that is, with different correspondences of nodes.

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

Hereinafter, transformations will be described in the right-handed $xyz$-coordinate system.

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

<image>

For the sample input 1, each node of the red tree is mapped to the corresponding node of the blue tree by the transformation that translates $(-3, 0, 0)$, rotates $-\pi / 2$ around the $z$-axis, rotates $\pi / 4$ around the $x$-axis, and finally scales by $\sqrt{2}$. By 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)$, respectively. This is the only possible correspondence of the twin trees.

For the sample input 2, red nodes #1, #2, #3, and #4 can be mapped to blue nodes #6, #5, #7, and #8. Another node correspondence exists that maps nodes #1, #2, #3, and #4 to #6, #5, #8, and #7.

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

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



Input

The input consists of a single test case of the following format.


$n$
$x_1$ $y_1$ $z_1$
.
.
.
$x_n$ $y_n$ $z_n$
$u_1$ $v_1$
.
.
.
$u_{n−1}$ $v_{n−1}$
$x_{n+1}$ $y_{n+1}$ $z_{n+1}$
.
.
.
$x_{2n}$ $y_{2n}$ $z_{2n}$
$u_n$ $v_n$
.
.
.
$u_{2n−2}$ $v_{2n−2}$


The input describes two trees. The first line contains an integer $n$ representing the number of nodes of each tree ($3 \leq n \leq 200$). Descriptions of two trees follow.

Description of a tree consists of $n$ lines that give the vertex positions and $n - 1$ lines that show the connection relation of the vertices.

Nodes are numbered $1$ through $n$ for the first tree, and $n + 1$ through $2n$ for the second tree.

The triplet $(x_i, y_i, z_i)$ gives the coordinates of the node numbered $i$. $x_i$, $y_i$, and $z_i$ are integers in the range between $-1000$ and $1000$, inclusive. Nodes of a single tree have distinct coordinates.

The pair of integers $(u_j , v_j )$ means that an edge exists between nodes numbered $u_j$ and $v_j$ ($u_j \ne v_j$). $1 \leq u_j \leq n$ and $1 \leq v_j \leq n$ hold for $1 \leq j \leq n - 1$, and $n + 1 \leq u_j \leq 2n$ and $n + 1 \leq v_j \leq 2n$ hold for $n \leq j \leq 2n - 2$.

Output

Output the number of different node correspondences if two trees are twins. Output a zero, otherwise.

Sample Input 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


Sample Output 1


1


Sample Input 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


Sample Output 2


2


Example

Input

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


Output

1

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>

constexpr long double EPSILON = 1e-9;
bool approx_equals(const long double a, const long double b) {
	return std::abs(a - b) < std::max(EPSILON, std::max(a, b) * EPSILON);
}
struct Point {
	long double x, y, z;
	long double distance2(const Point& that) const;
};
struct Vector {
	long double x, y, z;
	Vector cross(const Vector& that) const;
	long double norm() const;
};
Vector operator-(const Point& a, const Point& b);
Vector operator/(const Vector& v, const long double scale);
Point operator+(const Vector& v, const Point& p) {
	return Point{ v.x + p.x, v.y + p.y, v.z + p.z };
}
bool is_on_line(const Point& a, const Point& b, const Point& c)
{
	return approx_equals((a - b).cross(c - b).norm(), 0);
}

int round_to_int(const long double& value) {
	throw "REMOVE";
	return static_cast<int>(std::round(value));
}
using Edges = std::vector<std::pair<int, int>>;
using Tuple3 = std::tuple<long double, long double, long double>;
using Normalized = std::vector<Tuple3>;
Normalized normalize(const std::vector<Point>& points, int origin, int a, int b) {
	assert(origin != a && origin != b && a != b);
	const auto first = points[a] - points[origin];
	const auto second = points[b] - points[origin];
	const auto third = first.cross(second) / second.norm();
	const auto h1 = first + points[origin];
	const auto h2 = second + points[origin];
	const auto h3 = third + points[origin];
	Normalized result; result.reserve(points.size());
	for (const auto p : points) {
		result.emplace_back(h1.distance2(p), h2.distance2(p), h3.distance2(p));
	}
	return result;
}
bool comparator(const Tuple3& a, const Tuple3& b) {
	if (!approx_equals(std::get<0>(a), std::get<0>(b))) return std::get<0>(a) < std::get<0>(b);
	if (!approx_equals(std::get<1>(a), std::get<1>(b))) return std::get<1>(a) < std::get<1>(b);
	return std::get<2>(a) < std::get<2>(b);
}
bool operator==(const Tuple3& a, const Tuple3& b) {
	return approx_equals(std::get<0>(a), std::get<0>(b)) && approx_equals(std::get<1>(a), std::get<1>(b)) && approx_equals(std::get<2>(a), std::get<2>(b));
}
bool operator!=(const Tuple3& a, const Tuple3& b) {
	return !(a == b);
}
Tuple3 operator*(const Tuple3& a, const long long int scale) {
	return std::make_tuple(std::get<0>(a) * scale, std::get<1>(a) * scale, std::get<2>(a) * scale);
}
bool is_congruent(const Normalized& vertex_a, const Edges& edges_a, const Normalized& vertex_b, const Edges& edges_b, long double scale2_a, long double scale2_b) {
	const int size = vertex_a.size();
	std::vector<int> r_to_i_a(size), r_to_i_b(size), i_to_r_a(size), i_to_r_b(size);
	std::iota(r_to_i_a.begin(), r_to_i_a.end(), 0); std::iota(r_to_i_b.begin(), r_to_i_b.end(), 0);
	std::sort(r_to_i_a.begin(), r_to_i_a.end(), [&vertex_a](int i, int j) {return comparator(vertex_a[i], vertex_a[j]); });
	std::sort(r_to_i_b.begin(), r_to_i_b.end(), [&vertex_b](int i, int j) {return comparator(vertex_b[i], vertex_b[j]); });
	for (auto r = 0; r < size; ++r) {
		if (vertex_a[r_to_i_a[r]] * scale2_b != vertex_b[r_to_i_b[r]] * scale2_a) {
			return false;
		}
		i_to_r_a[r_to_i_a[r]] = r;
		i_to_r_b[r_to_i_b[r]] = r;
	}
	std::set<int> set;
	for (const auto e : edges_a) {
		auto a = i_to_r_a[e.first];
		auto b = i_to_r_a[e.second];
		if (a > b) {
			auto temp = b;
			b = a;
			a = temp;
		}
		set.insert(a * size + b);
	}
	for (const auto e : edges_b) {
		auto a = i_to_r_b[e.first];
		auto b = i_to_r_b[e.second];
		if (a > b) {
			auto temp = b;
			b = a;
			a = temp;
		}
		if (set.find(a * size + b) == set.end())
			return false;
	}
	return true;
}
bool is_congruent(const Point& a_first, const Point& b_first, const Point& c_first, const Point& a_second, const Point& b_second, const Point& c_second) {
	const auto abf = a_first.distance2(b_first);
	const auto bcf = b_first.distance2(c_first);
	const auto caf = c_first.distance2(a_first);
	const auto abs = a_second.distance2(b_second);
	const auto bcs = b_second.distance2(c_second);
	const auto cas = c_second.distance2(a_second);
	return approx_equals(bcf * abs, abf * bcs) && approx_equals(caf * abs, abf * cas);
}
struct Tree {
	std::vector<Point> points;
	Edges edges;
	std::vector<int> pair_of, leaf;
	Tree(std::vector<Point> _points, Edges _edges) : points{ std::move(_points) }, edges{ std::move(_edges) }, pair_of(points.size()) {
		std::vector<int> demension(points.size(), 0);
		for (auto& e : edges) {
			demension[--e.first]++;
			demension[--e.second]++;
			pair_of[e.first] = e.second;
			pair_of[e.second] = e.first;
		}
		for (auto i = 0; i < demension.size(); ++i) {
			if (demension[i] == 1) {
				leaf.push_back(i);
			}
		}
	}
};
int count_transform(const Tree& a, const Tree& b) {
	const auto first = a.leaf.front();
	const auto second = a.pair_of[first];
	auto third = -1;
	for (auto i = 0; i < a.points.size(); ++i) if (i != first && i != second) {
		if (third == -1) third = i;
		else if (!is_on_line(a.points[first], a.points[second], a.points[i])) third = i;
	}
	auto normarized_a = normalize(a.points, first, second, third);
	int count = 0;
	for (const auto first_b : b.leaf) {
		const auto second_b = b.pair_of[first_b];
		for (auto third_b = 0; third_b < b.points.size(); ++third_b) if (third_b != first_b && third_b != second_b) {
			if (is_congruent(a.points[first], a.points[second], a.points[third], b.points[first_b], b.points[second_b], b.points[third_b])) {
				auto normarized_b = normalize(b.points, first_b, second_b, third_b);
				if (is_congruent(normarized_a, a.edges, normarized_b, b.edges, a.points[first].distance2(a.points[second]), b.points[first_b].distance2(b.points[second_b])))
					++count;
			}
		}
	}
	return count;
}

int main() {
	int n; std::cin >> n;
	std::vector<Point> ap(n), bp(n);
	Edges ae(n - 1), be(n - 1);
	for (auto& p : ap) {
		std::cin >> p.x >> p.y >> p.z;
	}
	for (auto& e : ae) {
		std::cin >> e.first >> e.second;
	}
	for (auto& p : bp) {
		std::cin >> p.x >> p.y >> p.z;
	}
	for (auto& e : be) {
		std::cin >> e.first >> e.second;
		e.first -= n; e.second -= n;
	}
	std::cout << count_transform(Tree(ap, ae), Tree(bp, be)) << '\n';

}

long double Point::distance2(const Point& that) const
{
	return (that.x - x) * (that.x - x) + (that.y - y) * (that.y - y) + (that.z - z) * (that.z - z);
}

Vector Vector::cross(const Vector& that) const
{
	return Vector{ y * that.z - z * that.y, z * that.x - x * that.z, x * that.y - y * that.x };
}

long double Vector::norm() const
{
	return std::sqrt(x * x + y * y + z * z);
}

Vector operator-(const Point& a, const Point& b)
{
	return Vector{ static_cast<long double>(a.x) - b.x, static_cast<long double>(a.y) - b.y, static_cast<long double>(a.z) - b.z };
}

Vector operator/(const Vector& v, const long double scale)
{
	return Vector{ static_cast<long double>(v.x) / scale, static_cast<long double>(v.y) / scale, static_cast<long double>(v.z) / scale };
}