E - Swap Places Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 を出力せよ。

入力例 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

出力例 1

3
-1
3

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

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

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

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

Score : 500 points

Problem Statement

There is a simple undirected graph with N vertices numbered 1 through N and M edges numbered 1 through M. Edge i connects vertex u_i and vertex v_i.
Every vertex is painted either red or blue. The color of vertex i is represented by C_i; vertex i is painted red if C_i is 0 and blue if C_i is 1.

Now, Takahashi is on vertex 1 and Aoki is on vertex N.
They may repeat the following move zero or more times.

  • Each of the two simultaneously moves to a vertex adjacent to the current vertex.
    Here, the vertices that Takahashi and Aoki move to must have different colors.

By repeating the move above, can Takahashi and Aoki simultaneously end up on vertices N and 1, respectively?
If it is possible, find the minimum number of moves required. If it is impossible, print -1.

You are given T at the beginning of the input. Solve the problem for T test cases.

Constraints

  • 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
  • The graph given in the input is simple.
  • All values in the input are integers.
  • The sum of N over all test cases does not exceed 2000.
  • The sum of M over all test cases does not exceed 2000.

Input

The input is given from Standard Input in the following format, where \text{test}_i denotes the i-th test case:

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

Each test case is given in the following format:

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

Output

Print T lines. The i-th line should contain the answer to the i-th test case.
For each test case, print the minimum number of moves required for Takahashi and Aoki to simultaneously end up in vertices N and 1, respectively, if it is possible, and -1 otherwise.

Sample Input 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

Sample Output 1

3
-1
3

For the 1-st test case, Takahashi and Aoki can achieve the objective by making the following 3 moves, which is the minimum number:

  • Takahashi moves to vertex 3, and Aoki moves to vertex 2.
  • Takahashi moves to vertex 2, and Aoki moves to vertex 3.
  • Takahashi moves to vertex 4, and Aoki moves to vertex 1.

Note that in the 1-st move, it is disallowed that both Takahashi and Aoki move to vertex 2 (because the colors of vertices that Takahashi and Aoki move to must be different.)

For the 2-nd case, no matter how they move, they cannot achieve the objective.