Treequivalence

Time limit1sMemory limit128 MB

Summary

Given two textual tree notations, decide whether they describe the same unrooted planar drawing, allowing any root and cyclic order around each vertex.

Level: Hard8 of 10
Topics: Tree, Hash map, DFS, Recursion
Solved: No attempts yet

Problem

The following grammar describes a textual notation for a tree whose vertices carry labels (the labels need not be unique):

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

In other words, the notation for a tree is either a single label (an uppercase letter) or a label followed by a comma-separated, bracketed, ordered list of subtrees.

To draw such a tree on paper, we write every label on the page so that the subtrees of a vertex are arranged counter-clockwise around that vertex, and we join each vertex to each of its subtrees with non-intersecting line segments. That is, we draw the usual planar picture of the tree while preserving the given order of subtrees. Apart from these rules, the position, shape, and size of the picture are arbitrary.

For example, one drawing of A(B(C,D),E) places B and E counter-clockwise around A, and C and D counter-clockwise around B.

Given the textual notation for two trees, decide whether they are equivalent — that is, whether they can share one and the same paper drawing.

Two notations describe the same drawing when one picture can be read as both. Because the drawing has no marked root, you may start reading it from any vertex; and because its position and orientation on the page are free, the subtrees around a vertex are fixed only up to their cyclic (counter-clockwise) order. Flipping the paper over is not allowed: a mirror image reverses the counter-clockwise order and is a different drawing.

Input

The first line contains $t$ , the number of test cases. Each test case consists of two lines, each giving one tree in the notation above. Every such line contains at most 200 characters and no whitespace.

Output

For each test case, print a single line containing same if the two trees can share a paper drawing, or different otherwise.

Examples3

Example 1

Input

2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))

Expected output

different
same

Example 2
Input
```
2
A
A
A
B
```
Expected output
```
same
different
```

Example 3

Input

3
X(A,B,C)
X(C,A,B)
X(A,B,C)
X(A,C,B)
A(B,C)
B(A(C))

Expected output

same
different
same