H. Heading to Graduation
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Marina is in the final stretch of her degree at UFBA. After years of balancing classes, deadlines, and endless cups of coffee, she has only one goal left: graduate as soon as possible.

To do that, she must complete all $$$N$$$ required disciplines of her curriculum, numbered from $$$1$$$ to $$$N$$$. At first, her plan seemed simple: whenever a semester begins, she would enroll in every discipline she is already allowed to take. There is no villain in this story, no unexpected internship, no exchange program, and no dramatic plot twist. There is only Marina, her graduation requirements, and the one force capable of turning any peaceful academic plan into chaos: SIGAA.

Some disciplines, of course, depend on others. There are $$$M$$$ prerequisite relations, and each relation $$$(u, v)$$$ means that Marina must complete discipline $$$u$$$ before she is allowed to take discipline $$$v$$$. In principle, this should define a sensible curriculum structure. In practice, when SIGAA is involved, Marina would not be entirely surprised if somehow a later discipline ended up demanding an earlier one, which then demanded another one, which eventually demanded the first again.

As if that were not enough, not every discipline is offered every semester. Sometimes departments change plans, sometimes classes do not open, and sometimes SIGAA behaves in ways that students prefer not to question too deeply. There are $$$K$$$ temporary restrictions, and each restriction $$$(j, x)$$$ means that discipline $$$x$$$ is not offered in semester $$$j$$$. So even if Marina is fully ready to take a discipline, SIGAA may simply decide that semester is not the chosen one.

In any semester, Marina may take any number of disciplines, as long as:

  • every prerequisite of each chosen discipline was completed in an earlier semester, and
  • the discipline is offered in that semester.

Help Marina determine the minimum number of semesters she needs to finish all disciplines, survive the bureaucratic maze, and finally graduate. If graduation is impossible, output $$$-1$$$ and accept that Marina will remain trapped in UFBA forever, eventually becoming yet another legendary campus animal.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 2 \times 10^{5}$$$, $$$0 \leq M \leq 2 \times 10^{5}$$$).

The next $$$M$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq N$$$, $$$u \neq v$$$), meaning that discipline $$$u$$$ must be completed before discipline $$$v$$$.

The next line contains one integer $$$K$$$ ($$$0 \leq K \leq 2 \times 10^{5}$$$).

The next $$$K$$$ lines each contain two integers $$$j$$$ and $$$x$$$ ($$$1 \leq j \leq N + K$$$, $$$1 \leq x \leq N$$$), meaning that discipline $$$x$$$ is not offered in semester $$$j$$$.

It's guaranteed that all prerequisite pairs are distinct. Additionally, all restriction pairs are distinct.

Output

Output a single integer: the minimum number of semesters needed to complete all disciplines, or $$$-1$$$ if it is impossible.

Examples
Input
4 3
1 3
2 3
3 4
2
2 3
3 4
Output
4
Input
3 3
1 2
2 3
3 1
0
Output
-1
Note