The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 148 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

graphs

shortest paths

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Meeting Her

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputUrpal lives in a big city. He has planned to meet his lover tonight.

The city has *n* junctions numbered from 1 to *n*. The junctions are connected by *m* directed streets, all the roads have equal length. Urpal lives in junction *a* and the date is planned in a restaurant in junction *b*. He wants to use public transportation to get to junction *b*. There are *k* bus transportation companies. At the beginning of every second, a bus from the *i*-th company chooses a random shortest path between junction *s*_{i} and junction *t*_{i} and passes through it. There might be no path from *s*_{i} to *t*_{i}. In that case no bus will leave from *s*_{i} to *t*_{i}. If a bus passes through a junction where Urpal stands, he can get on the bus. He can also get off the bus at any junction along the path.

Now Urpal wants to know if it's possible to go to the date using public transportation in a finite amount of time (the time of travel is the sum of length of the traveled roads) and what is the minimum number of buses he should take in the worst case.

At any moment Urpal knows only his own position and the place where the date will be. When he gets on the bus he knows only the index of the company of this bus. Of course Urpal knows the city map and the the pairs (*s*_{i}, *t*_{i}) for each company.

Note that Urpal doesn't know buses velocity.

Input

The first line of the input contains four integers *n*, *m*, *a*, *b* (2 ≤ *n* ≤ 100; 0 ≤ *m* ≤ *n*·(*n* - 1); 1 ≤ *a*, *b* ≤ *n*; *a* ≠ *b*).

The next *m* lines contain two integers each *u*_{i} and *v*_{i} (1 ≤ *u*_{i}, *v*_{i} ≤ *n*; *u*_{i} ≠ *v*_{i}) describing a directed road from junction *u*_{i} to junction *v*_{i}. All roads in the input will be distinct.

The next line contains an integer *k* (0 ≤ *k* ≤ 100). There will be *k* lines after this, each containing two integers *s*_{i} and *t*_{i} (1 ≤ *s*_{i}, *t*_{i} ≤ *n*; *s*_{i} ≠ *t*_{i}) saying there is a bus route starting at *s*_{i} and ending at *t*_{i}. Please note that there might be no path from *s*_{i} to *t*_{i}, this case is described in the problem statement.

Output

In the only line of output print the minimum number of buses Urpal should get on on his way in the worst case. If it's not possible to reach the destination in the worst case print -1.

Examples

Input

7 8 1 7

1 2

1 3

2 4

3 4

4 6

4 5

6 7

5 7

3

2 7

1 4

5 7

Output

2

Input

4 4 1 2

1 2

1 3

2 4

3 4

1

1 4

Output

-1

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2024 17:17:23 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|