AT_abc277_e [ABC277E] Crystal Switches

[problemUrl]: https://atcoder.jp/contests/abc277/tasks/abc277_e $ N $ 個の頂点と $ M $ 本の辺からなる無向グラフが与えられます。 $ i\ =\ 1,\ 2,\ \ldots,\ M $ について、$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結ぶ無向辺であり、 $ a_i\ =\ 1 $ ならばはじめは通行可能、$ a_i\ =\ 0 $ ならばはじめは通行不能です。 また、頂点 $ s_1 $ 、頂点 $ s_2 $ 、$ \ldots $ 、頂点 $ s_K $ の $ K $ 個の頂点にはスイッチがあります。 高橋君は、はじめ頂点 $ 1 $ におり、「下記の**移動**と**スイッチを押す**の $ 2 $ つの行動のどちらかを行うこと」を好きなだけ繰り返します。 - **移動** : いまいる頂点と通行可能な辺を介して隣接する頂点を $ 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 $ に到達するまでに行う**移動**の回数としてあり得る最小値を出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ K\ \leq\ N $ - $ 1\ \leq\ u_i,\ v_i\ \leq\ N $ - $ u_i\ \neq\ v_i $ - $ a_i\ \in\ \lbrace\ 0,\ 1\rbrace $ - $ 1\ \leq\ s_1\ \lt\ s_2\ \lt\ \cdots\ \lt\ s_K\ \leq\ N $ - 入力はすべて整数 ### Sample Explanation 1 高橋君は、下記の手順で行動することで頂点 $ N $ に到達できます。 - 頂点 $ 1 $ から頂点 $ 2 $ に移動する。 - 頂点 $ 2 $ から頂点 $ 3 $ に移動する。 - 頂点 $ 3 $ にあるスイッチを押す。これによって、グラフ上のすべての辺の通行可能・通行不能の状態が反転する。 - 頂点 $ 3 $ から頂点 $ 1 $ に移動する。 - 頂点 $ 1 $ から頂点 $ 4 $ に移動する。 - 頂点 $ 4 $ にあるスイッチを押す。これによって、グラフ上のすべての辺の通行可能・通行不能の状態が再び反転する。 - 頂点 $ 4 $ から頂点 $ 5 $ に移動する。 この手順における移動の回数は $ 5 $ 回であり、これが考えられる最小の回数です。 ### Sample Explanation 2 与えられるグラフは、連結でないことや、多重辺を含むことがあります。 この入力例では、高橋君はどのように行動しても頂点 $ N $ に到達することはできないので、$ -1 $ を出力します。