{"problem":{"name":"Crystal Switches","description":{"content":"You are given an undirected graph consisting of $N$ vertices and $M$ edges.   For $i = 1, 2, \\ldots, M$, the $i$\\-th edge is an undirected edge connecting vertex $u_i$ and $v_i$ that is initially pass","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc277_e"},"statements":[{"statement_type":"Markdown","content":"You are given an undirected graph consisting of $N$ vertices and $M$ edges.  \nFor $i = 1, 2, \\ldots, M$, the $i$\\-th edge is an undirected edge connecting vertex $u_i$ and $v_i$ that is initially passable if $a_i = 1$ and initially impassable if $a_i = 0$. Additionally, there are switches on $K$ of the vertices: vertex $s_1$, vertex $s_2$, $\\ldots$, vertex $s_K$.\nTakahashi is initially on vertex $1$, and will repeat performing one of the two actions below, **Move** or **Hit Switch**, which he may choose each time, as many times as he wants.\n\n*   **Move**: Choose a vertex adjacent to the vertex he is currently on via an edge, and move to that vertex.\n*   **Hit Switch**: If there is a switch on the vertex he is currently on, hit it. This will invert the passability of every edge in the graph. That is, a passable edge will become impassable, and vice versa.\n\nDetermine whether Takahashi can reach vertex $N$, and if he can, print the minimum possible number of times he performs **Move** before reaching vertex $N$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq M \\leq 2 \\times 10^5$\n*   $0 \\leq K \\leq N$\n*   $1 \\leq u_i, v_i \\leq N$\n*   $u_i \\neq v_i$\n*   $a_i \\in \\lbrace 0, 1\\rbrace$\n*   $1 \\leq s_1 \\lt s_2 \\lt \\cdots \\lt s_K \\leq N$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$u_1$ $v_1$ $a_1$\n$u_2$ $v_2$ $a_2$\n$\\vdots$\n$u_M$ $v_M$ $a_M$\n$s_1$ $s_2$ $\\ldots$ $s_K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc277_e","tags":[],"sample_group":[["5 5 2\n1 3 0\n2 3 1\n5 4 1\n2 1 1\n1 4 0\n3 4","5\n\nTakahashi can reach vertex $N$ as follows.\n\n*   Move from vertex $1$ to vertex $2$.\n*   Move from vertex $2$ to vertex $3$.\n*   Hit the switch on vertex $3$. This inverts the passability of every edge in the graph.\n*   Move from vertex $3$ to vertex $1$.\n*   Move from vertex $1$ to vertex $4$.\n*   Hit the switch on vertex $4$. This again inverts the passability of every edge in the graph.\n*   Move from vertex $4$ to vertex $5$.\n\nHere, Move is performed five times, which is the minimum possible number."],["4 4 2\n4 3 0\n1 2 1\n1 2 0\n2 1 1\n2 4","\\-1\n\nThe given graph may be disconnected or contain multi-edges. In this sample input, there is no way for Takahashi to reach vertex $N$, so you should print $-1$."]],"created_at":"2026-03-03 11:01:13"}}