{"problem":{"name":"Moving Pieces on Graph","description":{"content":"You are given a simple connected undirected graph with $N$ vertices and $M$ edges, where the vertices are numbered $1$ to $N$ and the edges are numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc191_d"},"statements":[{"statement_type":"Markdown","content":"You are given a simple connected undirected graph with $N$ vertices and $M$ edges, where the vertices are numbered $1$ to $N$ and the edges are numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$ in both directions.\nInitially, there is a piece A on vertex $S$ and a piece B on vertex $T$. Here, $S$ and $T$ are given as input.\nYou may perform the following operation any number of times in any order:\n\n*   Choose either piece A or piece B, and move it from its current vertex to an adjacent vertex via an edge. However, you cannot make a move that results in both pieces ending up on the same vertex.\n\nYour goal is to reach the state in which piece A is on vertex $T$ and piece B is on vertex $S$.\nDetermine whether this is possible, and if it is, find the minimum number of operations required to achieve it.\n\n## Constraints\n\n*   $2 \\le N \\le 2\\times 10^5$\n*   $\\displaystyle N-1 \\le M \\le \\min\\left(\\frac{N(N-1)}{2},\\,2\\times 10^5\\right)$\n*   $1 \\le u_i < v_i \\le N$\n*   The given graph is simple and connected.\n*   $1 \\le S, T \\le N$\n*   $S \\neq T$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $S$ $T$\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":"arc191_d","tags":[],"sample_group":[["4 4 3 4\n2 4\n1 4\n3 4\n2 3","3\n\nFor example, the following sequence of operations completes the goal in three moves:\n\n1.  Move piece A to vertex $2$.\n    *   Piece A is on vertex $2$, piece B is on vertex $4$.\n2.  Move piece B to vertex $3$.\n    *   Piece A is on vertex $2$, piece B is on vertex $3$.\n3.  Move piece A to vertex $4$.\n    *   Piece A is on vertex $4$, piece B is on vertex $3$.\n\nIt is impossible to complete the goal in fewer than three moves, so print $3$."],["2 1 1 2\n1 2","\\-1\n\nNo matter how you move the pieces, you cannot achieve the goal."],["5 6 3 5\n1 2\n2 3\n1 5\n2 4\n1 3\n2 5","4"]],"created_at":"2026-03-03 11:01:13"}}