{"problem":{"name":"8 Puzzle on Graph","description":{"content":"Takahashi found a puzzle along some road.   It is composed of an undirected graph with nine vertices and $M$ edges, and eight pieces. The nine vertices of the graph are called Vertex $1$, Vertex $2$, ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc224_d"},"statements":[{"statement_type":"Markdown","content":"Takahashi found a puzzle along some road.  \nIt is composed of an undirected graph with nine vertices and $M$ edges, and eight pieces.\nThe nine vertices of the graph are called Vertex $1$, Vertex $2$, $\\ldots$, Vertex $9$. For each $i = 1, 2, \\ldots, M$, the $i$\\-th edge connects Vertex $u_i$ and Vertex $v_i$.  \nThe eight pieces are called Piece $1$, Piece $2$, $\\ldots$, Piece $8$. For each $j = 1, 2, \\ldots, 8$, Piece $j$ is on Vertex $p_j$.  \nHere, it is guaranteed that all pieces are on distinct vertices. Note that there is exactly one _empty_ vertex without a piece.\nTakahashi can do the following operation on the puzzle any number of times (possibly zero).\n\n> Choose a piece on a vertex adjacent to the empty vertex, and move it to the empty vertex.\n\nBy repeating this operation, he aims to _complete_ the puzzle. The puzzle is considered complete when the following holds.\n\n*   For each $j = 1, 2, \\ldots, 8$, Piece $j$ is on Vertex $j$.\n\nDetermine whether it is possible for Takahashi to complete the puzzle. If it is possible, find the minimum number of operations needed to do so.\n\n## Constraints\n\n*   $0 \\leq M \\leq 36$\n*   $1 \\leq u_i, v_i \\leq 9$\n*   The given graph has no multi-edges or self-loops.\n*   $1 \\leq p_j \\leq 9$\n*   $j \\neq j' \\Rightarrow p_j \\neq p_{j'}$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$M$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$\n$p_1$ $p_2$ $\\ldots$ $p_8$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc224_d","tags":[],"sample_group":[["5\n1 2\n1 3\n1 9\n2 9\n3 9\n3 9 2 4 5 6 7 8","5\n\nThe following procedure completes the puzzle in five operations.\n\n1.  Move Piece $2$ from Vertex $9$ to Vertex $1$.\n2.  Move Piece $3$ from Vertex $2$ to Vertex $9$.\n3.  Move Piece $2$ from Vertex $1$ to Vertex $2$.\n4.  Move Piece $1$ from Vertex $3$ to Vertex $1$.\n5.  Move Piece $3$ from Vertex $9$ to Vertex $3$.\n\nOn the other hand, it is impossible to complete the puzzle in less than five operations. Thus, we should print $5$.  \nNote that the given graph may not be connected."],["5\n1 2\n1 3\n1 9\n2 9\n3 9\n1 2 3 4 5 6 7 8","0\n\nThe puzzle is already complete from the beginning. Thus, the minimum number of operations needed to complete the puzzle is $0$."],["12\n8 5\n9 6\n4 5\n4 1\n2 5\n8 9\n2 1\n3 6\n8 7\n6 5\n7 4\n2 3\n1 2 3 4 5 6 8 7","\\-1\n\nNo sequence of operations can complete the puzzle, so we should print $-1$."],["12\n6 5\n5 4\n4 1\n4 7\n8 5\n2 1\n2 5\n6 9\n3 6\n9 8\n8 7\n3 2\n2 3 4 6 1 9 7 8","16"]],"created_at":"2026-03-03 11:01:13"}}