트리 동등성

다음 문법은 각 정점에 라벨이 붙은 트리(라벨은 서로 달라야 할 필요가 없다)를 나타내는 텍스트 표기법을 정의한다.

tree ::= label
tree ::= label ( subtrees )
subtrees ::= tree
subtrees ::= subtrees , tree
label ::= A | B | C | ... | Z

즉, 한 트리의 표기는 하나의 라벨(대문자 한 글자)이거나, 라벨 뒤에 괄호로 묶이고 쉼표로 구분된 부분트리들의 순서 있는 목록이 오는 형태이다.

이러한 트리를 종이에 그릴 때는, 각 라벨을 종이에 적되 한 정점의 부분트리들이 그 정점을 중심으로 반시계 방향으로 놓이도록 배치하고, 각 정점과 그 부분트리들을 서로 교차하지 않는 선분으로 잇는다. 다시 말해, 주어진 부분트리 순서를 유지한 채 트리의 일반적인 평면 그림을 그린다. 이 규칙 외에는 그림의 위치·모양·크기를 임의로 정해도 된다.

예를 들어 A(B(C,D),E)의 한 그림은, A의 둘레에 B와 E를 반시계 방향으로 두고, B의 둘레에 C와 D를 반시계 방향으로 둔 모습이다.

두 트리의 텍스트 표기가 주어질 때, 두 트리가 동등한지, 즉 하나의 동일한 종이 그림을 공유할 수 있는지 판정하여라.

두 표기가 같은 그림을 나타낸다는 것은, 하나의 그림을 두 표기 모두로 읽어낼 수 있다는 뜻이다. 그림에는 지정된 루트가 없으므로 어느 정점에서부터 읽기 시작해도 되고, 종이 위의 위치와 방향은 자유로우므로 한 정점 둘레의 부분트리들은 (반시계 방향의) 순환 순서까지만 정해진다. 다만 종이를 뒤집는 것은 허용되지 않는다. 거울상은 반시계 방향 순서를 뒤바꾸므로 서로 다른 그림이다.

첫째 줄에 테스트 케이스의 수 $t$가 주어진다. 각 테스트 케이스는 두 줄로 이루어지며, 각 줄에는 위 표기법으로 나타낸 트리가 하나씩 주어진다. 각 줄은 최대 200개의 문자로 이루어지고 공백을 포함하지 않는다.

각 테스트 케이스마다, 두 트리가 하나의 종이 그림을 공유할 수 있으면 same을, 그렇지 않으면 different를 한 줄에 출력한다.