在某个直播间里，观众常常会发送类似这样的弹幕：

鱼越大，鱼刺越大；鱼刺越大，肉越少；肉越少，鱼越小；所以鱼越大，鱼越小
这样通过一连串推导得出一个搞笑的结论的弹幕发送者被称为“相对论大师”。

现在给定一系列已有的推论，请你从给定的推论中挑选一些，组成一条类似于上面的弹幕，成为一名“相对论大师”。

输入格式:
输入第一行是一个正整数 N (1≤N≤1000），表示总共有多少条推论。

接下来的 N 行，每行有两对四个元素，形如下：

A 0 B 1
每对元素表示一个论点：第一个是一个长度不大于 5 的、只包含大小写字母的字符串，称为论点的核心；第二个数字固定为 0 或者 1，代表论点核心的方向属性。为简单理解，你可以将 0 理解为正面方向，1 理解为负面方向。例如：

YuCi 0 Rou 1

就可以理解为鱼刺大，肉少 。

于是一行中的两个论点就形成一条推论，表示第一个核心某个方向的属性能推出第二个核心的某个方向的属性，即鱼刺越大，肉越少。

输出格式:
按照弹幕格式输出一行，例如：

Yu 0 YuCi 0 YuCi 0 Rou 1 Rou 1 Yu 1 = Yu 0 Yu 1
具体格式要求为：在一行中输出从起始论点到最终论点的所有推论，论点格式与输入相同，论点间以1个空格分隔。随后输出等号（等号前后均有1个空格），最后是相互矛盾的起始和终止论点。

如果有多种方案，选择使用推论最少的；推论条数相同的输出任意一种方案均可。

在方案中每条推论仅可使用一次。保证有解，且给定的推论中没有相同的推论。

输入样例:
5
Yu 0 Yuci 0
Rou 1 Yu 1
Yuci 0 Rou 1
Yuci 0 Gutou 0
Gutou 0 Rou 0

输出样例:
Yu 0 Yuci 0 Yuci 0 Rou 1 Rou 1 Yu 1 = Yu 0 Yu 1

#include <bits/stdc++.h>
using namespace std;
const int N=2010;  //注意可能有双向边 
int h[N],e[N],ne[N],idx;
int fa[N];   //存储i节点的父节点，在bfs的过程中存储，可以记录路径，同时可以表示节点是否被走过
string name[N];  //存储每个论点的节点编号 （yu 0的节点编号为x，则yu 1的节点编号为x+1） 
int cnt=1;  //节点编号，因为图的每个节点为字符串，所以需要自己建立节点编号
unordered_map<string,int>mp;  //存储基本节点的编号(1,3,5,7,9...) ，建立编号与字符串的映射

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

//bfs找出从start起点到end终点的最短路径
vector<int>bfs(int start,int end)
{
    queue<int>q;
    memset(fa,0,sizeof fa);   //注意要清空上一次的bfs，因为起点不同，到终点的最短路径不同 
    q.push(start); 

    while(q.size())
    {
        auto t=q.front();
        if(t==end)  break;   //剪枝，到终点提前退出 
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(fa[j]==0)   //若儿子节点的父节点还未标记，则说明还未走过
            {
                q.push(j);
                fa[j]=t;
            }
        }
    }
    vector<int>c;
    //先将终点放入 
    do{
        c.push_back(end);
        end=fa[end];
    }while(end!=0);   //注意这里是 end!=0，不是fa[end]!=0 
    return c;
}

int main()
{
    int n;cin>>n;
    memset(h,-1,sizeof h);
    while(n--)
    {
        string s1,s2;
        int a,b;
        cin>>s1>>a>>s2>>b;
        //因为每个相反的论点的字符串是连续存储的，一次存储这两个论点，
        //且mp只需存0论点的节点，
        //若之前存储过，就不用再存储该论点的字符串和映射
        if(!mp.count(s1))   
        {
            mp[s1]=cnt;
            name[cnt]=s1;
            name[++cnt]=s1;
            cnt++;
        }
        if(!mp.count(s2))
        {
            mp[s2]=cnt;
            name[cnt]=s2;
            name[++cnt]=s2;
            cnt++;
        }
        if(a==0)    a=mp[s1];
        else    a+=mp[s1];
        if(b==0)    b=mp[s2];
        else    b+=mp[s2];
        add(a,b);
    }

    vector<int>res(2010);
    //把每个论点作为起点
    for(int i=1;i<=cnt-2;i+=2)
    {
        auto x=bfs(i,i+1);
        auto y=bfs(i+1,i);
        //注意size>1，因为有的可能到达不了终点
        if(x.size()<res.size()&&x.size()>1)    res=x;
        if(y.size()<res.size()&&y.size()>1)    res=y;
    }

    for(int i=res.size()-1;i>=1;i--)
    {
        //mp存的是0的论点的节点编号，且0论点的节点编号小1，所以0论点输出0，1论点输出1
        cout<<name[res[i]]<<' '<<res[i]-mp[name[res[i]]]<<' ';
        cout<<name[res[i-1]]<<' '<<res[i-1]-mp[name[res[i-1]]]<<' ';
    }
    cout<<"= ";
    cout<<name[res[res.size()-1]]<<' '<<res[res.size()-1]-mp[name[res[res.size()-1]]]<<' '<<name[res[0]]<<' '<<res[0]-mp[name[res[0]]];
    return 0;
}