有一个简单的无向图，有 N个顶点，编号为 1到 N和 M条边，编号为 1到 M. 边缘 i连接着顶点 u i 和顶点 v i . 每个顶点都被涂成红色或蓝色。顶点的颜色 i的颜色由 C i 表示；顶点 i被涂成红色，如果 C i 是 0，蓝色，如果 C i 是 1. 现在，高桥在顶点 1，而青木在顶点 N. 他们可以重复以下动作0次或更多次。 两人中的每一个都同时移动到与当前顶点相邻的一个顶点。 这里，高桥和青木移动到的顶点必须有不同的颜色。 通过重复上面的移动，高桥和青木能否同时在顶点上结束 N和 1？ 如果可以，求出所需的最小移动次数。如果不可能，则打印-1。 你将得到 T在输入的开头。求解该问题的 T测试案例。

这是一道图论问题，给定一个无向图，要求找到从顶点1到顶点N的最短路径，使得路径上的点的颜色都不同。

解决这个问题的方法是使用双端队列进行广搜。首先将顶点1插入队列，然后每次取出队列的队首，如果队首为顶点N，则说明找到了答案；如果没有，则将该顶点的所有相邻点中颜色不同于该顶点的点加入队列，并且将该顶点的步数加1。

求解时间复杂度为O(M + N)，其中M为边的数量，N为顶点的数量。

代码实现如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int head[N<<1],tot,dis[N<<1];
bool vis[N<<1];
struct node
{
    int to,nxt;
}edge[N<<2];
inline void add(int u,int v)
{
    edge[++tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
int n,m,s,t,ans;
void bfs()
{
    queue<int> q;
    q.push(s);
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int v=edge[i].to;
            if(dis[v]==dis[u]+1)
            {
                if(v==t)
                {
                    cout<<dis[t]/2<<endl;
                    return;
                }
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    cout<<-1<<endl;
    return;
}