题目描述

頂点に $1$ から $N$ までの、辺に $1$ から $M$ までの番号がついた $N$ 頂点 $M$ 辺の単純無向グラフがあります。 辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を結んでいます。
また、全ての頂点は赤か青のいずれか一方で塗られています。頂点 $i$ の色は $C_i$ で表されて、$C_i$ が $0$ ならば頂点 $i$ は赤く、$1$ ならば頂点 $i$ は青く塗られています。

今、高橋君が頂点 $1$ に、青木君が頂点 $N$ にいます。
2 人は次の行動を $0$ 回以上好きな回数繰り返します。

• 2 人が同時に、今いる頂点に隣接している頂点のいずれか 1 個に移動する。
  ただし、高橋君の移動先の頂点の色と、青木君の移動先の頂点の色は異なる必要がある。

上記の行動を繰り返すことで、高橋君が頂点 $N$ に、青木君が頂点 $1$ にいる状態にできますか？
可能である場合は必要な行動回数の最小値を答えてください。不可能である場合は -1 を出力してください。

入力のはじめに $T$ が与えられるので、$T$ 個のテストケースについて問題を解いてください。

输入格式

入力は以下の形式で標準入力から与えられる。ここで $\text{test}_i$ は $i$ 番目のテストケースを意味する。

$T$ $\text{test}_1$ $\text{test}_2$ $\vdots$ $\text{test}_T$

各テストケースは以下の形式で与えられる。

$N$ $M$ $C_1$ $C_2$ $\dots$ $C_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出格式

$T$ 行出力せよ。$i$ 行目には $i$ 番目のテストケースに対する答えを出力せよ。
各テストケースでは、高橋君が頂点 $N$ に、青木君が頂点 $1$ にいる状態にできる場合は必要な行動回数の最小値を、できない場合は -1 を出力せよ。

题目大意

给定一个 $n$ 个点 $m$ 条边的无向图，满足 $1\le n,m\le 2\times 10^3$。点有点权，值可以为 $0$ 或 $1$。两个人分别在点 $1$ 和 $n$，每次他们同时向自己这个结点的任意一个邻居移动，任意时刻，他们所在的结点的权值不得相同。最后要使得他们互相交换位置。

请求出最小次数，如果无解，输出 $-1$。

3
4 4
0 1 0 1
1 2
2 3
1 3
2 4
3 3
0 1 0
1 2
2 3
1 3
6 6
0 0 1 1 0 1
1 2
2 6
3 6
4 6
4 5
2 4

3
-1
3

提示

制約

• $1\ \leq\ T\ \leq\ 1000$
• $2\ \leq\ N\ \leq\ 2000$
• $1\ \leq\ M\ \leq\ \min(\frac{N(N-1)}{2},\ 2000)$
• $C_i\ \in\ \lbrace\ 0,\ 1\ \rbrace$
• $1\ \leq\ u_i,\ v_i\ \leq\ N$
• 入力で与えられるグラフは単純
• 入力される値は全て整数
• 全てのテストケースに対する $N$ の総和は $2000$ を超えない。
• 全てのテストケースに対する $M$ の総和は $2000$ を超えない。

Sample Explanation 1

1 番目のテストケースでは、高橋君と青木君は以下のように行動することで、 $3$ 回の行動で目的の状態を達成することができて、これが最小です。 - 高橋君が頂点 $3$ に、青木君が頂点 $2$ に移動する。 - 高橋君が頂点 $2$ に、青木君が頂点 $3$ に移動する。 - 高橋君が頂点 $4$ に、青木君が頂点 $1$ に移動する。 ここで、$1$ 回目の移動で高橋君と青木君がともに頂点 $2$ に移動することはできないのに注意してください。(なぜならば、高橋君の移動先の頂点の色と青木君の移動先の頂点の色は異なる必要があるからです。) 2 番目のテストケースでは、2 人はどのように行動しても目的の状態を達成することはできません。