乌帕尔住在一座大城市。他计划今晚去见他的爱人。
该城市有 n 个路口,编号从 1 到 n。这些路口由 m 个有向街道连接,所有道路的长度相等。 Urpal 住在 A 路口,约会计划在 B 路口的一家餐厅进行。他想乘坐公共交通工具到达 b 路口。有 k 家巴士运输公司。在每一秒的开始,第 i 个公司的公交车会在交叉路口 si 和交叉路口 ti 之间选择一条随机最短路径并通过它。从 si 到 ti 可能没有路径。在这种情况下,不会有巴士从 si 开往 ti。如果公交车经过乌帕尔所在的路口,他就可以上车。他还可以在沿途的任何路口下车。
现在Urpal想知道是否可以在有限的时间内使用公共交通前往约会地点(行程时间是所行驶道路长度的总和),以及在最坏的情况下他应该乘坐的最少公共汽车数量是多少。
乌帕尔在任何时候都只知道他自己的位置和约会地点。当他上车时,他只知道这辆公交车公司的索引。当然,Urpal 知道城市地图和每个公司的配对 (si, ti)。
请注意,Urpal 不知道公交车速度。
输入
输入的第一行包含四个整数 n、m、a、b (2 ≤ n ≤ 100;0 ≤ m ≤ n·(n - 1);1 ≤ a、b ≤ n;a ≠ b)。
接下来的 m 行包含两个整数,每个 ui 和 vi (1 ≤ ui, vi ≤ n; ui ≠ vi) 描述从交汇点 ui 到交汇点 vi 的有向道路。输入中的所有道路都是不同的。
下一行包含一个整数 k (0 ≤ k ≤ 100)。此后将有 k 条线,每条线包含两个整数 si 和 ti(1 ≤ si,ti ≤ n;si ≠ ti),表示有一条从 si 开始到 ti 结束的公交路线。请注意,从 si 到 ti 可能没有路径,这种情况在问题陈述中进行了描述。
输出
在输出的唯一一行中,打印出 Urpal 在最坏情况下应该上路的最少巴士数量。如果在最坏的情况下也无法到达目的地,则打印-1。
示例
输入 #1
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
输出 #1
2
输入 #2
4 4 1 2 1 2 1 3 2 4 3 4 1 1 4
输出 #2
-1