J. Less Time on the Road
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Moonland City can be viewed as a directed graph, and the lengths of all the edges are $$$1$$$. Alice and Bob are the only two pipe workers in the city. Whenever there is a request from a vertex, a pipe worker must go to the vertex to fix the pipe there, while the other one stays still. Today they received a list of requests, and they must complete these requests one by one in the given order. In the beginning, Alice and Bob are all at vertex 1. Neither Alice nor Bob wants to take too much time on the road, so they find you to help them minimize $$$\max\{S_A, S_B\}$$$, where $$$S_A$$$ is the total distance Alice needs to go and $$$S_B$$$ is the total distance Bob needs to go.

Input

The first line contains two integers $$$n, m$$$ $$$(2 \leq n \leq 80, n \leq m \leq n(n-1))$$$, which are the number of vertices and the number of edges in the graph, respectively.

The next $$$m$$$ lines each contain three integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n, u \neq v)$$$, which means there is an edge from vertex $$$u$$$ to vertex $$$v$$$.

The next line contains an integer $$$q$$$ $$$(1 \leq q \leq 80)$$$, which is the number of requests.

The next line contains $$$q$$$ integers $$$x_1, x_2, \dots, x_q$$$ $$$(1 \leq x_i \leq n)$$$, which are the vertices in the request list in order.

It is guaranteed that the graph is strongly connected, that is, there is a path from any vertex to any other vertex.

Output

Output a single integer, which is the minimum $$$\max\{S_A, S_B\}$$$.

Examples
Input
3 4
1 3
3 1
1 2
2 3
3
2 1 3
Output
1
Input
5 7
2 1
1 4
3 5
1 2
3 1
5 4
4 3
5
4 2 4 1 5
Output
3