{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"4 4 3 4\n2 4\n1 4\n3 4\n2 3"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"2 1 1 2\n1 2"},{"iden":"sample output 2","content":"\\-1\n\nNo matter how you move the pieces, you cannot achieve the goal."},{"iden":"sample input 3","content":"5 6 3 5\n1 2\n2 3\n1 5\n2 4\n1 3\n2 5"},{"iden":"sample output 3","content":"4"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}