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

~^\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~.

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.