水晶开关

题目描述

给定一个由 $N$ 个顶点和 $M$ 条边组成的无向图。

对于 $i = 1, 2, \ldots, M$,第 $i$ 条边是连接顶点 $u_i$ 和 $v_i$ 的无向边;当 $a_i = 1$ 时初始可通行,当 $a_i = 0$ 时初始不可通行。 此外,在 $K$ 个顶点上有开关:顶点 $s_1$、顶点 $s_2$、$\ldots$、顶点 $s_K$。

高桥初始位于顶点 $1$,他会按自己的意愿重复执行以下两种操作之一任意次。

移动:选择一条与当前所在顶点相邻的边,沿该边移动到所连接的顶点。

按开关:如果当前所在顶点上有开关,按下它。这会使图中所有边的可通行性反转,即可通行的边变得不可通行,反之亦然。

判断高桥能否到达顶点 $N$,如果能,输出在到达顶点 $N$ 之前执行移动操作的最少次数。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $K$
$u_1$ $v_1$ $a_1$
$u_2$ $v_2$ $a_2$
$\vdots$
$u_M$ $v_M$ $a_M$
$s_1$ $s_2$ $\ldots$ $s_K$

输出格式

如果高桥无法到达顶点 $N$,输出 $-1$; 如果能够到达,输出在到达顶点 $N$ 之前执行移动操作的最少次数。

样例

5 5 2
1 3 0
2 3 1
5 4 1
2 1 1
1 4 0
3 4

5

高桥可以按如下方式到达顶点 $N$。

• 从顶点 $1$ 移动到顶点 $2$。
• 从顶点 $2$ 移动到顶点 $3$。
• 按下顶点 $3$ 上的开关,图中所有边的可通行性被反转。
• 从顶点 $3$ 移动到顶点 $1$。
• 从顶点 $1$ 移动到顶点 $4$。
• 按下顶点 $4$ 上的开关,图中所有边的可通行性再次被反转。
• 从顶点 $4$ 移动到顶点 $5$。

这里移动操作执行了 $5$ 次,这是最少次数。

4 4 2
4 3 0
1 2 1
1 2 0
2 1 1
2 4

-1

给定的图可能不连通,也可能包含重边。在本样例中,高桥无法到达顶点 $N$,因此应输出 $-1$。

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $0 \le K \le N$
• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$
• $a_i \in \lbrace 0, 1\rbrace$
• $1 \le s_1 \lt s_2 \lt \cdots \lt s_K \le N$
• 输入中的所有值均为整数。