飞机票： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=990

由于昨天有事。。。所以没怎么细想。。。然后一直以为只要深度相同。。。然后子节点个数相同就可以了。。。然后就一直Wa。。。后来自己把自己的想法推翻了。。。直接看下图：

然后这里的话。。。如果按我起先的想法肯定是wa的因为1层都有2个子节点。二层有3个节点和2个节点。三层有2，0，0，3，0个节点

但是这两棵树明显不同、、debug爽啊。。。接着我的想法就是。。。那把每个节点的深度算出来和他的子树节点的深度都算出来。。。然后排序比较。。。这个想法明显是正确。。但是速度不快啊~~~囧。然后百度了一下。。。有一种方法是跟括号匹配差不多。。。就是说经过父节点（，回到了父节点就），然后括号里面的可以交换位置。。。交换出最小字典序。。。然后比较是否相同，还有一种方法：好像说是只要把深度算出来然后计算子树节点数排序比较就可以了。。。但是为什么呢。。感觉也不怎么对。。。画个图。。。其实这个想法是错误的

这个的序列是0010101001011100101011和0010101010101100010111。。。然而这个是diff。但是前面的跑出来的是same。。所以错误的。。。估计测试数据没有这个数据。我还是不传输错误的代码了。。。就用那个速度慢的吧

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#define LL long long
using namespace std;
const int maxn=3456;
char ch[2][maxn];
struct he
{
    int dep;
    vector<int> V;
} JLJ[2][1567];
void init()
{
    scanf("%s%s",ch[0]+1,ch[1]+1);
}
int idx,st, p;
int len;
void DFS(int now,int dep)
{
    JLJ[p][now].dep=dep;
    while(idx<=len&&ch[p][idx]=='0')
    {
        idx++;
        st++;
        int q=st;
        DFS(q,dep+1);
        for(int j=0; j<JLJ[p][q].V.size(); j++)
        {
            JLJ[p][now].V.push_back(JLJ[p][q].V[j]+1);
        }
    }

    JLJ[p][now].V.push_back(0);
    sort(JLJ[p][now].V.begin(),JLJ[p][now].V.end());
    idx++;
    return;

}
bool cmp(he a,he b)
{
    if(a.dep!=b.dep)return a.dep<b.dep;
    if(a.V.size()!=b.V.size())return a.V.size()<b.V.size();
    for(int i=0; i<a.V.size(); i++)
    {
        if(a.V[i]>b.V[i])
        {
            return 1;
        }
        else if(a.V[i]<b.V[i])
        {
            return 0;
        }
    }
    return 0;
}
void play()
{
    if(strlen(ch[0]+1)!=strlen(ch[1]+1))
    {
        printf("different\n");
        return;
    }
    len=strlen(ch[0]+1);
    for(int i=0; i<=len/2; i++)
    {
        JLJ[0][i].dep=0;
        JLJ[0][i].V.clear();
        JLJ[1][i].dep=0;
        JLJ[1][i].V.clear();
    }
    idx=1;
    st=0;
    p=0;
    DFS(0,0);
    idx=1;
    st=0;
    p=1;
    DFS(0,0);
    sort(JLJ[0],JLJ[0]+st+1,cmp);
    sort(JLJ[1],JLJ[1]+st+1,cmp);
    //cout<<st<<endl;
    for(int i=0; i<=st; i++)
    {
        if(JLJ[0][i].dep!=JLJ[1][i].dep)
        {
            printf("different\n");
            return;
        }
        if(JLJ[0][i].V.size()!=JLJ[1][i].V.size())
        {
            printf("different\n");
            return;
        }
        for(int j=0; j<JLJ[0][i].V.size(); j++)
        {
            if(JLJ[0][i].V[j]!=JLJ[1][i].V[j])
            {
                printf("different\n");
                return;
            }
        }

    }
    printf("same\n");
}
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}