{"problem":{"name":"Swap Places","description":{"content":"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc289_e"},"statements":[{"statement_type":"Markdown","content":"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$.  \nEvery 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$.\nNow, Takahashi is on vertex $1$ and Aoki is on vertex $N$.  \nThey may repeat the following move zero or more times.\n\n*   Each of the two simultaneously moves to a vertex adjacent to the current vertex.  \n    Here, the vertices that Takahashi and Aoki move to must have different colors.\n\nBy repeating the move above, can Takahashi and Aoki simultaneously end up on vertices $N$ and $1$, respectively?  \nIf it is possible, find the minimum number of moves required. If it is impossible, print `-1`.\nYou are given $T$ at the beginning of the input. Solve the problem for $T$ test cases.\n\n## Constraints\n\n*   $1 \\leq T \\leq 1000$\n*   $2 \\leq N \\leq 2000$\n*   $1 \\leq M \\leq \\min(\\frac{N(N-1)}{2}, 2000)$\n*   $C_i \\in \\lbrace 0, 1 \\rbrace$\n*   $1 \\leq u_i, v_i \\leq N$\n*   The graph given in the input is simple.\n*   All values in the input are integers.\n*   The sum of $N$ over all test cases does not exceed $2000$.\n*   The sum of $M$ over all test cases does not exceed $2000$.\n\n## Input\n\nThe input is given from Standard Input in the following format, where $\\text{test}_i$ denotes the $i$\\-th test case:\n\n$T$\n$\\text{test}_1$\n$\\text{test}_2$\n$\\vdots$\n$\\text{test}_T$\n\nEach test case is given in the following format:\n\n$N$ $M$\n$C_1$ $C_2$ $\\dots$ $C_N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc289_e","tags":[],"sample_group":[["3\n4 4\n0 1 0 1\n1 2\n2 3\n1 3\n2 4\n3 3\n0 1 0\n1 2\n2 3\n1 3\n6 6\n0 0 1 1 0 1\n1 2\n2 6\n3 6\n4 6\n4 5\n2 4","3\n-1\n3\n\nFor the $1$\\-st test case, Takahashi and Aoki can achieve the objective by making the following $3$ moves, which is the minimum number:\n\n*   Takahashi moves to vertex $3$, and Aoki moves to vertex $2$.\n*   Takahashi moves to vertex $2$, and Aoki moves to vertex $3$.\n*   Takahashi moves to vertex $4$, and Aoki moves to vertex $1$.\n\nNote 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.)\nFor the $2$\\-nd case, no matter how they move, they cannot achieve the objective."]],"created_at":"2026-03-03 11:01:14"}}