Metro#1725
Some cities have a metro network structured like a tree, meaning there is exactly one path between any two stations. These networks have a unique central station. Imagine you are a tourist in such a city, eager to explore the entire metro network. You start at the central station, randomly choose a direction, and travel to the next station. Each time you reach a station, you select one of the branches you haven't traveled on yet. If there are no unexplored branches left at a station, you return to the station from which you arrived at this station for the first time. This process continues until you have traversed all branches twice (once in each direction). At this point, you will be back at the central station. Such a journey can be represented as a binary string: the digit 0 represents a trip moving away from the central station, and the digit 1 represents a trip moving closer to the central station. Multiple encoding strings can represent the same metro network since unexplored branches are chosen randomly.
Write a program to determine whether two binary strings describe the same metro network.
The first line of the input contains an integer (1 \leq N \leq 20) — the number of test cases. Then, pairs of strings follow, each consisting of the digits and , with a maximum length of characters.
Each line encodes one valid exploration of the metro network.
For each pair of strings, print "same" if both strings encode the exploration of the same metro network, or "different" if the explored metro networks are different.
Example 1