配点 : $500$ 点

問題文

頂点に $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$ 個のテストケースについて問題を解いてください。

制約

• $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$ を超えない。

入力

入力は以下の形式で標準入力から与えられる。ここで $\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 を出力せよ。

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 番目のテストケースでは、高橋君と青木君は以下のように行動することで、 $3$ 回の行動で目的の状態を達成することができて、これが最小です。

• 高橋君が頂点 $3$ に、青木君が頂点 $2$ に移動する。
• 高橋君が頂点 $2$ に、青木君が頂点 $3$ に移動する。
• 高橋君が頂点 $4$ に、青木君が頂点 $1$ に移動する。

ここで、$1$ 回目の移動で高橋君と青木君がともに頂点 $2$ に移動することはできないのに注意してください。(なぜならば、高橋君の移動先の頂点の色と青木君の移動先の頂点の色は異なる必要があるからです。)

2 番目のテストケースでは、2 人はどのように行動しても目的の状態を達成することはできません。