题目描述

给定一个无向图和若干标号棋子。图有 V 个顶点、M 条边，顶点从 1..V 编号，其中有 V-1 枚棋子分别标号为 1..V-1，且初始时每个棋子放置在不同的顶点上，剩余一个顶点为空。

一次操作为：选择一个与空顶点相邻的顶点上的棋子，将该棋子移动到空顶点上（即与空位交换位置）。操作次数不限。

当对于所有 j=1..V-1，棋子 j 位于顶点 j 时，认为拼图完成。请判断能否完成；若可以，输出完成所需的最少操作次数，否则输出 -1。

输入格式

V M
u_1 v_1
u_2 v_2
…
u_M v_M
p_1 p_2 … p_{V-1}

其中 u_i v_i 表示一条无向边连结顶点 u_i 与 v_i；p_j 表示棋子 j 的初始所在顶点。

输出格式

输出一个整数：最少操作次数；若无法完成输出 -1。

数据范围与子任务

• 子任务 1（10%）：V = 2
• 子任务 2（40%）：V = 5
• 子任务 3（50%）：V = 9
• 统一约束：0 ≤ M ≤ V(V-1)/2，无自环与重边；1 ≤ p_j ≤ V，且彼此不同；输入均为整数。

样例

输入：

5 7
1 2
1 4
2 3
2 4
2 5
3 4
4 5
5 4 2 1

输出：

6