高桥在路上捡到了一个谜题玩具，这个谜题由 $9$ 个顶点 $M$ 条无向边，和 $8$ 个棋子组成。顶点编号为 $1 \sim 9$，第 $i$ 条边连接顶点 $u_i$ 和$v_i$，棋子编号为 $1 \sim 8$。图没有重边和自环。

初始状态下，编号 $j$ 的棋子在编号 $p_j$ 顶点上，每个顶点最多只能有一个棋子。每次移动，可以将一个棋子移动到和它相邻的没有棋子的顶点上。相邻指的是两个顶点之间有一条边直接连接。

如果对 $j=1 \sim 8$，编号 $j$ 的棋子都移动到了编号 $j$ 的顶点上，这个谜题就解开了。

问高桥最少需要几次移动才能解开谜题。如果无法解开谜题，输出 $-1$ 。