A7166 | 午枫的数字华容道

小午最近买了一个数字华容道，数字华容道是一个由 $3\times3$ 组成的方格，其中有数字 $1\sim8$ 被放置在不同的格子当中，有一个格子是空的，空格子的上下左右四个位置的格子可以通过移动填充到空格子当中，移动之前的位置将变为空格子，目标是将 $3\times 3$ 的格子从左到右从上到下依次变为 $1,2,3,\cdots,8$ ，最后一个格子为空格子。

但是小午并不满足与此，他在原版的数字华容道上进行了改造，改造后的数字华容道可以形式化的表述为：

华容道中有 $9$ 顶点和 $m$ 条边组成的无向图，以及有 $8$ 个数字，其中 $9$ 个顶点编号为 $1\sim 9$ ，对于第 $i$ 条边，连接顶点 $u_i$ 和 $v_i$ 。$8$ 个数字分别为 $1\sim 8$ ，对于数字 $i$ ，被放置在顶点 $p_i$ 上。保证所有棋子都放在不同的顶点上。其中有且仅有一个没有数字的空顶点。

现在小枫可以对这个华容道进行以下操作任意次：

+ 选择一个与空顶点相邻的顶点上的数字，将这个数字移动到空顶点上。

小枫想通过重复以上操作完成这个数字华容道。当满足以下状态时，数字华容道被认为是完成的：

+ 对于 $i=1,2,\cdots,8$ ，数字 $i$ 被放置在顶点 $i$ 上。

请判断小枫能否完成数字华容道。如果可以，输出完成所需的最小操作次数；如果无法完成，请输出 -1 。

第一行输入一个正整数 $m$ $(0\leq m\leq 36)$ ，表示华容道中边的数量。

接下来 $m+1$ 行，每行输入两个整数 $u_i,v_i$ $(1\leq u_i,v_i\leq9)$ ，表示第 $i$ 条边连接的两个顶点。保证没有重边和自环。

最后一行输入 $8$ 个整数 $p_i$ $(1\leq p_i\leq 9)$ ，表示数字 $i$ 起是被放置在顶点 $p_i$ 上。

如果小枫可以完成数字华容道，输出完成所需的最小操作次数；如果无法完成，请输出 -1 。