有一个简单的无向图，有 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。

如果图是二分图，您可以使用BFS来求出最短路径。在BFS中，每次移动高桥和青木到相邻的不同颜色顶点，并累加移动次数。在最后，您可以返回移动的次数。

下面是用C++代码实现的例子：

#include <bits/stdc++.h>
using namespace std;

const int N=10010;
int T,n,m,s,t;
int h[N],e[N<<1],ne[N<<1],idx;
int dist[N];
bool st[N];
int color[N];

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

bool bfs()
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);