题目描述

拓拓在路上碰到了一个谜题。

它由 $9$ 个节点的无向图组成，编号 $1,2,...,9$。同时有 $M$ 条边，编号 $1,2,...,M$。其中第 $i$ 条边，连接 $u_i$ 和 $v_i$ 节点。有八件物品分别在不同的节点上，其中第 $j$ 件物品在 $p_j$ 节点上。

这里保证每件物品都在不同的节点上。所以，有且只有一个节点是空的，没有物品。

拓拓可以完成下面的操作，并且可以做任意次（包括 $0$ 次）。

• 选择一件物品，将它移动到相邻的且没有物品的节点上。

通过重复操作，他试图解开这个谜题。解开的条件是：

• 对于所有 $j=1,2,...,8$，第 $j$ 件物品在第 $j$ 个节点上。

判断拓拓能否解开个这个谜题。如果有可能完成，找出最少需要几次操作。

输入格式

第一行一个整数 $M$。表示边的个数。

接下来 $M$ 行，每行两个整数 $u_i$ 和 $v_i$，用空格隔开,表示一条边连接的两个节点。

最后一行，$8$ 个整数 $p_1,p_2,...,p_8$ 代表开始时物品所在节点。

输出格式

如果拓拓可以解开谜题，输出所需的最小操作数。否则输出$-1$。

样例

5
1 2
1 3
1 9
2 9
3 9
3 9 2 4 5 6 7 8

5

下面$5$个操作可以解开谜题。

• 将物品 $2$ 到从节点 $9$ 移动到节点 $1$
• 将物品 $3$ 到从节点 $2$ 移动到节点 $9$
• 将物品 $2$ 到从节点 $1$ 移动到节点 $2$
• 将物品 $1$ 到从节点 $3$ 移动到节点 $1$
• 将物品 $3$ 到从节点 $9$ 移动到节点 $3$

同时，不可能用少于 $5$ 次的操作解开谜题。所以输出 $5$。

注意给定的图未必是连通的。

5
1 2
1 3
1 9
2 9
3 9
1 2 3 4 5 6 7 8

0

从一开始谜题就是解开状态，无需操作。所以输出 $0$。

12
8 5
9 6
4 5
4 1
2 5
8 9
2 1
3 6
8 7
6 5
7 4
2 3
1 2 3 4 5 6 8 7

-1

无论怎样操作都无法解开谜题。所以输出 $-1$。

12
6 5
5 4
4 1
4 7
8 5
2 1
2 5
6 9
3 6
9 8
8 7
3 2
2 3 4 6 1 9 7 8

16

数据范围

-输入数据保证有：

• $0≤M≤36$
• $1≤u_i,v_i≤9$
• 给定的图没有multi-edges(一对节点之间有多条边相连)和自环(一条边的两端都是同一个节点，自己指自己)
• $1≤p_j≤9$
• $j\neq j'⇒p_j\neq p_{j'}$