题目描述

有一个有 $N$ 个点 $M$ 条边的简单（无重边，无自环）无向图，点从 $1$ 到 $N$ 编号，边从 $1$ 到 $M$ 编号。边 $i$ 连接点 $u_i$ 和 $v_i$。 每个点被染成红色互蓝色。点 $i$ 的颜色用 $C_i$ 表示；若 $C_i = 0$ 则点 $i$ 是红色，若 $C_i = 1$ 则点 $i$ 是蓝色。 现在，高桥在点 $1$ 青木在点 $N$。他们可以重复下述动作零次或多次。 两人同时移动到与当前所在点相邻的一个点，并且二人移动到的点的颜色必须不同。 是否可能经过若干次移动后，高桥到达点 $N$，青木到达点 $1$？ 若可能，求出所需的最少移动次数，否则输出 -1。 一个输入文件里有 $T$ 个测试。 限制 $1≤T≤1000$ $2≤N≤2000$ $1≤M≤\min(N(N−1)/2, ,2000)$ $1≤u_i,v_i ≤N$ 全部测试的 $N$ 之和不超过 $2000$。  全部测试的 $M$ 之和不超过 $2000$。

输入格式

输入的格式

$T$

$test_1$

$test_2$

⋮

$test_T$

每个测试的格式

$N$ $M$

$C_1$ $C_2$ … $C_N$

$u_1$ $v_1$

$u_2$ $v_2$

⋮

$u_M$ $v_M$

输出格式

输出 $T$ 行。第 $i$ 行是第 $i$ 个测试的答案。

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