unordered_map<string, int> da, db;//记录某一个结点距离起点和终点的最短距离
queue<string> qa, qb;//维护双向BFS的两个队列：起点队列和终点队列 
/*
  extend为队列拓展数组，每一次调用extend()函数是为了依次扩展"某一层所有结点"的
  下一层所有子节点
  要扩展的"某一层所有结点"即为队列q中现存的所有结点，q即代表本轮extend中要拓展
  的队列 
  extend函数中的d1和d2： 
  如果q对应的是起点拓展的队列，那么d1对应到起点的距离，d2对应到终点的距离
  如果q对应的是终点拓展的队列，那么d1对应到终点的距离，d2对应到起点的距离，其实
  也就是从终点开始拓展，终点对应终点所拓展的点就相当于起点了
*/
int extend(queue<int> &q, unordered_map<string, int> &d1[], unordered_map<string, int> &d2[])
{
    int d = d1[q.front()];
/*
  while循环中的两个条件保证了本次extend函数中起点（或终点）某一层中所有结点都得
  到了扩展
  d1[q.front()]==d：因为同一层中所有结点距离起点（或终点）的距离是一样的，该条
  件保证了只扩展该层的所有结点，即扩展不了下一子层的结点 
*/
    while(q.size() && d1[q.front()] == d)
    {
        auto t = q.front();
        q.pop();
        for(...)//枚举结点t的所有子节点t_son 
        {
            //如果d2中已经存在结点t_son，说明找到了起点到终点的最短路径 
            if(d2.count(t_son))
            {
                return d2[t_son] + (d1[t] + 1);
            }
/*
  如果d2中不存在结点t_son，说明还未找到起点到终点的最短路径，那么就需要将t_son
  尝试加入到队列q中，即
  若t_son是从起点扩展来的就加入到起点队列qa中；
  若t_son是从终点扩展来的就加入到终点队列qb中 

  但如果要加入的队列（假设是起点队列）中已经有了t_son结点，说明t_son到起点的
  最短距离已经存在（即之前已经遍历到过），而本次扩展的t_son距离起点的距离不是
  最短距离（同普通bfs原理），因此不能加入到起点队列当中 
*/
            else if(d1.count(t_son)) continue;
/*
  相反，若起点队列中没有t_son结点，说明t_son结点是第一次被遍历到，即本轮t_son
  距离起点的距离即为最短距离 
*/
            else
            {
                d1[t_son] = d[t] + 1;
                q.push(t_son);
            }
        } 
    }
    return -1;
}
int bfs()
{
    int t;//记录起终的最短路径 
    while(qa.size() && qb.size())
    {
        //从结点少的队列开始拓展时间复杂度较小
        //因为结点少的队列，它拓展出来的分支也少
        //从而能避免枚举那些无意义的字符串
        if(qa.size() < qb.size()) t = extend(qa, da, db);
        else t = extend(qb, db, da);
        if(t != -1) return t;//说明起终最短路径t已经找到    
    }
    return -1;//说明起终不通路 
}