CF238E.Meeting Her

Urpal 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.

乌尔帕尔住在一个大城市里。他计划今晚与恋人约会。

这座城市共有 $n$ 个路口，编号从 $1$ 到 $n$。这些路口由 $m$ 条有向街道连接，所有道路长度相等。乌尔帕尔住在路口 $a$，而约会地点是一家位于路口 $b$ 的餐厅。他打算乘坐公共交通工具前往路口 $b$。城市中有 $k$ 家公交公司。在每一秒的起始时刻，第 $i$ 家公司的公交车会随机选择一条从路口 $s_i$ 到路口 $t_i$ 的最短路径，并沿该路径行驶。可能存在从 $s_i$ 到 $t_i$ 的不可达情况；此时，将没有公交车从 $s_i$ 出发驶向 $t_i$。若某辆公交车经过乌尔帕尔所在的路口，他便可登上该车；此外，他也可以在路径上的任意路口下车。

现在，乌尔帕尔希望知道：是否能在有限时间内（旅行时间定义为所经道路长度之和）通过公共交通抵达约会地点？若可以，最坏情况下他至少需要换乘多少次公交车？

在任意时刻，乌尔帕尔仅知晓自己当前所处的位置以及约会地点的位置。当他登上一辆公交车时，他仅知道该车所属公司的编号。当然，乌尔帕尔事先已知整座城市的地图，以及每家公交公司对应的 $(s_i,\,t_i)$ 对。

注意：乌尔帕尔并不知道公交车的行驶速度。

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.

输入的第一行包含四个整数 $n$、$m$、$a$、$b$（满足 $2 \leq n \leq 100$；$0 \leq m \leq n \cdot (n - 1)$；$1 \leq a, b \leq n$；且 $a \neq b$）。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（满足 $1 \leq u_i, v_i \leq n$；$u_i \neq v_i$），表示一条从路口 $u_i$ 指向路口 $v_i$ 的有向道路。输入中所有道路互不相同。

接下来一行包含一个整数 $k$（满足 $0 \leq k \leq 100$）。此后将有 $k$ 行，每行包含两个整数 $s_i$ 和 $t_i$（满足 $1 \leq s_i, t_i \leq n$；$s_i \neq t_i$），表示存在一条从 $s_i$ 出发、在 $t_i$ 结束的公交线路。请注意，从 $s_i$ 到 $t_i$ 可能不存在路径，该情况已在题目描述中说明。

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.

在输出的唯一一行中，打印 Urpal 在最坏情况下需要乘坐的最少公交车数量。如果在最坏情况下无法到达目的地，则输出 -1。