该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

$TooY0ung$ 在玩一种不是很新的走格子游戏。

题目描述

棋盘上有从 $1$ 开始编号的 $n$ 个格子，$n$ 个格子由 $m$ 条边相连形成无向图，初始还有不超过 $3$ 个棋子在不同的格子内。

$TooY0ung$ 会对棋子进行多个回合的移动，当任意一个棋子到达终点 $e$ 时，游戏通关。

$TooY0ung$ 可以进行两种操作：

A、挑选一个棋子，将其移动到“相邻”的格子中；

B、挑选两个“相邻”的棋子，那么交换这两个棋子的位置。

请注意：

1、当两个格子之间存在一条边时，我们称两个格子“相邻”；

2、当两个棋子所处的格子“相邻”，我们称两个棋子“相邻”；

3、任何情况下，一个格子内都不允许出现两个或以上的棋子；

4、若棋盘中只有一个棋子，则不能进行操作$B$；

5、每个回合内，$TooY0ung$ 可以进行任意次数的B操作，但对每一个棋子只能进行至多一次的 $A$ 操作（也可以不进行）。

$TooY0ung$ 不想走格子，$TooY0ung$ 只想知道最少几个回合游戏可以通关。

请帮助 $TooY0ung$ 编写一个程序，计算出通关游戏的最少回合数，若没有任何一个棋子可以到达终点则输出 $-1$。

输入格式

第 $1$ 行：$3$ 个由空格分开的正整数 $n,m,t$，其中 $n$ 表示格子数量，$m$ 表示无向边的数量，$t$ 表示棋子的数量；

接下来的 $m$ 行：每行有 $2$ 个由空格分开的正整数 $a_i,b_i$，表示编号为 $a_i$ 的格子与编号为 $b_i$ 的格子之间有一条无向边；

第 $m+2$ 行：$t$ 个由空格分开的正整数 $s_i$，表示每个棋子初始所在的格子编号；

第 $m+3$ 行：$1$ 个正整数 $e$，表示终点格子的编号。

输出格式

共 $1$ 行：一个正整数，表示通关游戏的最少回合数，若没有任何一个棋子可以到达终点则输出 $-1$。

10 5 3
1 2
5 2
6 5
4 5
3 2
3 1 4
6

1

10 0 2
1 3
6

-1

10 7 3
7 6
1 6
6 5
2 5
2 6
3 2
4 5
3 1 4
7

2

提示

【样例解释1】

在样例 $1$ 中，一回合即可通关游戏：

对位于 $3$ 格子的棋子 $b$ 进行 $A$ 操作，将其移动至 $2$ 格子

对位于 $4$ 格子的棋子 $c$ 进行 $A$ 操作，将其移动至 $5$ 格子

对位于 $1$ 格子与 $2$ 格子的棋子 $a、b$ 进行 $B$ 操作，调换其位置

对位于 $2$ 格子与 $5$ 格子的棋子 $a、c$ 进行 $B$ 操作，调换其位置

对位于 $5$ 格子的棋子 $a$ 进行 $A$ 操作，将其移动至 $6$ 格子

数据规模与约定

对于 $100\%$ 的数据，$1 \le t \le 3$，$t \le a_i, b_i, s_i, e \le n \le 10^5$，$0 \le m \le 2*10^5$

数据保证不会出现自环、重复边；

数据保证不会有棋子出现在同一初始位置，不会有棋子初始出现在终点格子。