Given a directed graph ~G~ consisting of ~n~ vertices and ~m~ edges, where the ~i~-th edge connects vertex ~u_i~ to vertex ~v_i~. Additionally, you are given a walk ~P~ from vertex ~1~ to vertex ~n~ ~^\dagger~, using edges ~p_1, p_2, \ldots, p_k~ in that order.
You need to find the minimum number of edges that need to be removed from ~G~ for ~P~ to become the unique walk from vertex ~1~ to vertex ~n~. If there is no way to remove edges to satisfy the condition, print ~-1~.
~^\dagger~ A walk ~P~ from vertex ~1~ to vertex ~n~ is an ordered list of edge indices ~p_1, p_2, \dots, p_k~ such that:
~u_{p_1} = 1~.
~v_{p_i} = u_{p_{i + 1}}~ for every ~1 \le i < k~.
~v_{p_k} = n~.
Input
Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~). The description of each test case is as follows.
The first line contains three integers ~n~, ~m~, and ~k~ (~2 \le n \le 10^5~, ~1 \le m, k \le 10^5~) — the number of vertices and edges in the graph ~G~, and the number of edges in the walk ~P~.
The ~i~-th line among ~m~ next lines contains two integers ~u_i~ and ~v_i~ (~1 \le u_i, v_i \le n~, ~u_i \neq v_i~) — the ~i~-th edge of the graph ~G~.
The next line contains ~k~ integers ~p_1, p_2, \ldots, p_k~ (~1 \le p_i \le m~) representing a walk from ~1~ to ~n~. It is guaranteed that these edge indices form a walk from ~1~ to ~n~.
The sum of ~n~, the sum of ~m~, and the sum of ~k~ over all test cases are guaranteed not to exceed ~10^5~.
Output
For each test case, output an integer — the minimum number of edges that need to be removed for ~P~ to become the unique walk from vertex ~1~ to vertex ~n~. If there is no way to remove edges to satisfy the condition, print ~-1~.
Scoring
Subtask | Score | Constraints |
---|---|---|
1 | ~1000~ | ~n = m~, ~G~ is weakly connected ~^\ddagger~ |
2 | ~500~ | Sum of ~n~ does not exceed ~1000~, ~k = 1~, ~u_i \neq n~ and ~v_i \neq 1~ for all ~1 \le i \le m~ |
3 | ~1250~ | Sum of ~n~ does not exceed ~1000~ |
4 | ~500~ | No additional constraints |
Total | ~3250~ |
~^\ddagger~ A directed graph is weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.
Sample Input 1
3
5 5 4
1 3
3 2
4 3
2 4
4 5
1 2 4 5
5 6 3
1 2
2 3
3 5
3 1
4 3
1 4
6 5 3
5 5 5
1 2
2 3
3 4
4 2
2 5
1 2 3 4 5
Sample Output 1
1
2
-1
Notes
For the first test case, the following diagram shows the graph ~G~, with the walk ~P~ highlighted in red. We need to remove the third edge (corresponding to ~4 \to 3~), as there is the walk ~1 \to 3 \to 2 \to 4 \to 3 \to 2 \to 4 \to 5~ that uses this edge and goes from ~1~ to ~5~.
Illustration of the first test case.
For the second test case, the following diagram shows the graph ~G~, with the walk ~P~ highlighted in red. We need to remove the ~2 \to 3~ and the ~3 \to 1~ edges.
Illustration of the second test case.
Comments