P10477 · 地铁树

题目背景

若一个城市的地铁网络是树状结构（任意两站之间仅存在唯一一条路径），并且存在一个唯一的中央车站，那么从中央车站出发进行一次"把所有线路都走到、且每条边正反各走一次"的探索，会得到一段只记录"远离/接近中央车站"的二进制行程编码：

• 0：从当前站乘车到更远离中央车站的一站（向下，父→子）；
• 1：从当前站乘车到更近中央车站的一站（向上，子→父）。

这段编码等价于一次覆盖整棵树所有边的"上下行"轨迹（每条边走两次），最终回到中央车站。

题目描述

给定两个描述地铁树系统探索行程的二进制字符串，判断它们是否可能来源于同一个地铁树系统（同一棵无序有根树）。若可能，输出 same；否则输出 different。

输入格式

• 第一行：正整数 \(n\)，表示测试组数。

• 接下来 \(n\) 组数据，每组两行：

  • 第 1 行：一个仅由 '0' 和 '1' 组成的字符串 \(s_1\)；
  • 第 2 行：一个仅由 '0' 和 '1' 组成的字符串 \(s_2\)。

题目保证每个字符串均为合法行程编码（对应某棵以中央车站为根的树的一次完整探索）。

输出格式

对每组数据，若两串可表示同一个地铁树系统的探索行程，输出 same；否则输出 different。

数据范围与约定

• 每个行程字符串长度 \(\le 3000\)。
• 每个字符串均为合法编码：可视作一段"上下行"合法括号序列，并最终回到根。
• 需要比较的是无序有根树是否相同（兄弟先后顺序不重要）。

说明（理解用，不影响作答）

• 将 0 视作"下潜"、1 视作"回溯"，利用栈可把行程还原为一棵有根有序树；
• 为了比较无序形态，常用对子树进行规范化编码（例如对所有孩子的编码排序后拼接并加一层外壳）；
• 两棵树的根规范形相同，则认为代表同一地铁树系统。

上述内容仅为直觉说明，非唯一解法。

样例

输入

2
0010011101001011
0100011011001011
0100101100100111
0011000111010101

输出

same
different

样例解释（简述）

• 第 1 组：虽然两串访问兄弟的先后顺序可能不同，但对应的无序树形一致，故 same。
• 第 2 组：对应的树形不同，故 different。