쌍둥이 트리 형제

ICPC(International Cacao Plantation Consortium)의 요구를 충족하려면 주어진 두 트리가 쌍둥이인지 확인해야 한다.

3차원 공간에 있는 두 트리의 예시이다.

그래프 이론에서 트리는 연결된 그래프이며, 간선의 수가 정점의 수보다 1 작다. ICPC는 트리의 각 정점 위치를 3차원 격자점으로 준다. 두 트리가 쌍둥이라는 것은 한 트리의 모든 정점을 다른 트리의 정점에 일대일로 대응시키는 기하 변환 함수가 존재하고, 한 트리의 각 간선에 대해 대응하는 두 정점을 잇는 간선이 다른 트리에도 있다는 뜻이다. 기하 변환은 다음 변환의 조합이어야 한다.

• 평행 이동: 좌표값에 상수를 더한다.
• 균일 축척: 양의 축척 계수를 세 좌표값 모두에 같이 곱한다.
• 회전: x축, y축, z축 중 어느 축을 기준으로든 임의의 각도만큼 회전한다.

두 트리는 정점 대응이 서로 다르더라도 쌍둥이일 수 있다.

두 트리가 쌍둥이인지 판별하고, 서로 다른 정점 대응의 개수를 출력하는 프로그램을 작성하라.

변환은 오른손 좌표계인 xyz 좌표계를 기준으로 설명한다.

샘플 입력 1부터 4까지의 트리는 다음 그림과 같다. 그림의 숫자는 아래에서 정의하는 정점 번호이다.

샘플 입력 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에서는 한 트리의 정점을 다른 트리의 정점으로 옮기는 변환이 존재하지 않는다.

첫 줄에는 각 트리의 정점 수 $n$이 주어진다. 단, $3 \le n \le 200$이다. 이어서 두 트리에 대한 설명이 주어진다. 한 트리의 설명은 $n$개의 정점 위치 줄과 $n-1$개의 간선 줄로 이루어진다. 첫 번째 트리의 정점 번호는 1부터 $n$까지이고, 두 번째 트리의 정점 번호는 $n+1$부터 $2n$까지이다.

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

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

각 좌표 $x_i$, $y_i$, $z_i$는 $-1000$ 이상 $1000$ 이하의 정수이다. 같은 트리 안에서 정점 좌표는 모두 서로 다르다.

$(u_j, v_j)$는 정점 $u_j$와 $v_j$를 잇는 간선이 있다는 뜻이다. 단, $u_j \ne v_j$이다. 첫 번째 트리에서는 $1 \le u_j, v_j \le n$이고, 두 번째 트리에서는 $n+1 \le u_j, v_j \le 2n$이다.

두 트리가 쌍둥이이면 서로 다른 정점 대응의 개수를 출력한다. 그렇지 않으면 0을 출력한다.