树形地铁系统

题目描述

一些主要城市拥有树形的地铁系统，即在任何一对车站之间，有且只有一种方式可以乘坐地铁。

此外，这些城市大多数都有一个中央车站。

想象一下，你是一名在拥有树形地铁系统的城市游玩的游客，你想探索该城市完整的地铁线路。

你从中央车站出发，随机选择一条地铁线，然后乘坐地铁行进。

每次到达一个车站，你都将选择一条尚未乘坐过的地铁线路进行乘坐。

如果不存在未乘坐过的线路，则退回到上一个车站，再做选择。

直到你将所有地铁线路都乘坐过两次（往返各一次），此时你将回到中央车站。

之后，你以一种特殊的方式回忆自己的坐车过程，你将你的完整地铁乘坐路线编码为一个二进制字符串。

• 0 编码表示你乘坐地铁线路到达距离中央车站更远的一站
• 1 编码表示你乘坐地铁线路到达距离中央车站更近的一站

输入格式

第一行输入一个正整数 $n$，代表测试用例数量。

每个测试用例由两行组成，每行输入一个由字符 0 和 1 构成的字符串，长度最多为 $3000$。两个字符串都描述了一种树形地铁系统的正确探索路线。

输出格式

对于每个测试用例：

• 如果两个字符串描述的探索路线可以视为同一个地铁系统的两种探索路线，则输出 same。
• 否则，输出 different。

每行输出一个结果。

数据范围

• $n$ 为测试用例数量
• 每个字符串长度不超过 $3000$

输入样例

2
0010011101001011
0100011011001011
0100101100100111
0011000111010101

输出样例

same
different

样例解释

第一个测试用例：
两个字符串 0010011101001011 和 0100011011001011 描述的是同一个地铁系统，只是探索路线的选择顺序不同。

第二个测试用例：
两个字符串 0100101100100111 和 0011000111010101 描述的是不同的地铁系统，因此输出 different。

时空限制

• 时间限制：2秒
• 空间限制：64MB