트리 동형 판정

빌보(Bilbo)는 인생의 사랑인 오블립(Oblib)을 만났지만, 그녀가 어쩐지 낯익어 혹시 둘이 친척은 아닐까 걱정한다. 두 사람 모두 자신의 조상 계보는 알고 있지만, 그 계보를 곧바로 비교할 수는 없다. 빌보는 조상들의 이름을 남성형으로 알고 있고 오블립은 여성형으로 알고 있는데, 두 형태 사이에는 아무런 규칙적 대응이 없기 때문이다. 설령 둘이 남매라 해도, 서로가 아는 조상들의 이름은 모두 다를 것이다!

빌보와 오블립은 각자의 가계도를 적어 두었다. 당신의 과제는 두 트리가 동형(isomorphic)인지, 즉 이름을 무시하고 부모–자식 구조를 그대로 보존하는 노드 간 일대일 대응이 존재하는지 판정하는 것이다. 트리는 루트가 고정된(rooted) 트리이므로, 두 트리의 루트는 서로에게 대응되어야 한다.

예를 들어 아래 왼쪽의 두 트리는 동형이 아니다. a의 두 자식을 x의 두 자식에 대응시킬 방법이 없는데, a의 한 자식은 반드시 자기 자식을 둘 가져야 하지만 x의 어떤 자식도 그렇지 않기 때문이다.

동형이 아닌 트리	동형인 트리

반면 오른쪽의 두 트리는 동형이다. 한 가지 대응은 다음과 같다: a ↔ x(루트는 항상 서로 대응), b ↔ z, c ↔ y, g ↔ u, d ↔ w, e ↔ t, f ↔ v. d와 e의 대응을 맞바꾼 또 다른 동형 대응도 존재한다.

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다 ($T < 100$). 각 테스트 케이스는 두 줄로 이루어지며, 각 줄은 하나의 트리를 나타낸다.

트리는 루트에서 시작하는 전위 순회(pre-order traversal) 순서로 만난 노드 라벨들로 표현된다. 즉 루트에서 잎 방향으로, 그리고 왼쪽에서 오른쪽으로 트리를 따라가며 처음 방문하는 노드의 라벨을 출력한다. 한 노드의 모든 자식을 나열한 직후에는 그 노드를 닫는다는 의미로 해시 기호 #를 출력한다. 모든 라벨과 해시 기호는 하나의 공백으로 구분된다.

예를 들어 루트 a 아래에 자식 b(그 자식은 잎 d와 e)와 잎 c가 있는 트리는 a b d # e # # c # #로 적는다.

각 테스트 케이스마다 두 트리가 동형이면 The two trees are isomorphic.를, 동형이 아니면 The two trees are not isomorphic.를 출력한다. 각 줄은 줄바꿈으로 끝낸다.