Problem H
Eulerian Graphs 2

Your friend claims to have solved the problem Eulerian Graphs, and to one-up you even implemented an algorithm to supposedly find the kind of walks described! To remind you, that problem is about determining if a directed graph contains a walk that passes through each edge exactly once.

You strongly doubt your friend’s claim. After all, surely they can’t be further ahead in their algorithm training than you. The only explanation is that their algorithm is actually incorrect. Write a program that, given an input graph and a walk in the graph, determines if it is passes all the edges in the graph exactly once.

You should detect two error conditions. First, if the walk uses an edge that does not exist, you should find the earliest point the walk where this happens. This includes cases where the walk goes from one vertex to another that do have an edge between them, but the edge has already been passed. Keep in mind that the graph is allowed to contain multiple edges between the same pair of vertices, each of which must be passed exactly once.

Secondly, if the walk itself was valid, you must check if it actually passed through every edge.

Input

The first line contains integers $N$ ($2 \le N \le 100\, 000$), the number of vertices, and $M$ ($0 \le M \le 200\, 000$), the number of edges. This is followed by $M$ lines, one for each edge $a \rightarrow b$, containing the numbers $a$ and $b$ ($1 \le a, b \le N$).

The next line contains the integer $1 \le W \le 200\, 000$, the length of the walk in the graph. This is followed by a single line containing $W + 1$ vertex names $w_1, w_2, \dots , w_{W + 1}$. The walk consists of the edges $w_1 \rightarrow w_2$, $w_2 \rightarrow w_3$, $\dots $.

In this problem we do not guarantee that the graph is connected in any way, nor that vertices may not be isolated. As long as the walk passes through all edges, you should judge it as correct.

Output

If the walk is invalid, output the index of the first invalid edge (starting at $1$). Otherwise, if the walk does not pass through every edge, output too short. Otherwise, output correct.

2 4
1 2
2 2
1 1
2 1
4
1 2 2 1 1

correct

2 4
2 2
2 1
1 2
1 1
4
1 2 1 1 2

4

2 4
2 1
2 2
1 2
1 1
3
1 2 1 1

too short