Problem: 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 si and junction ti and passes through it. There might be no path from si to ti. In that case no bus will leave from si to ti. If a bus passes through a junction where Urpal stands, he can get on the bus. He can also get off 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 (si, ti) 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 ui and vi (1 ≤ ui, vi ≤ n; ui ≠ vi) describing a directed road from junction ui to junction vi. 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 si and ti (1 ≤ si, ti ≤ n; si ≠ ti) saying there is a bus route starting at si and ending at ti. Please note that there might be no path from si to ti, 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
struct DominatorTree {
  static const int maxn = 200 + 5;
  int n, rt;
  vector<int> adj1[maxn];
  vector<int> adj2[maxn];
  vector<int> tree[maxn];
  vector<int> bucket[maxn];
  int par[maxn];
  int sdm[maxn];
  int dom[maxn];
  int dsu[maxn];
  int lbl[maxn];
  int arr[maxn];
  int rev[maxn];
  int tms;
  void init(int n, int rt) {
    this->n = n;
    this->rt = rt;
    for (int i = 0; i < n; i++) {
      adj1[i].clear();
      adj2[i].clear();
      tree[i].clear();
      bucket[i].clear();
    }
    fill_n(arr, n, -1);
    tms = 0;
  }
  void add(int u, int v) { adj1[u].push_back(v); }
  void dfs(int u) {
    arr[u] = tms, rev[tms] = u;
    lbl[tms] = tms, sdm[tms] = tms, dsu[tms] = tms;
    tms++;
    for (int i = 0; i < (int)adj1[u].size(); i++) {
      int w = adj1[u][i];
      if (!~arr[w]) dfs(w), par[arr[w]] = arr[u];
      adj2[arr[w]].push_back(arr[u]);
    }
  }
  int find(int u, int x = 0) {
    if (u == dsu[u]) return x ? -1 : u;
    int v = find(dsu[u], x + 1);
    if (v < 0) return u;
    if (sdm[lbl[dsu[u]]] < sdm[lbl[u]]) {
      lbl[u] = lbl[dsu[u]];
    }
    dsu[u] = v;
    return x ? v : lbl[u];
  }
  void join(int u, int v) { dsu[v] = u; }
  void build() {
    dfs(rt);
    for (int i = tms - 1; i >= 0; i--) {
      for (int j = 0; j < (int)adj2[i].size(); j++) {
        sdm[i] = min(sdm[i], sdm[find(adj2[i][j])]);
      }
      if (i > 1) bucket[sdm[i]].push_back(i);
      for (int j = 0; j < (int)bucket[i].size(); j++) {
        int w = bucket[i][j], v = find(w);
        if (sdm[v] == sdm[w])
          dom[w] = sdm[w];
        else
          dom[w] = v;
      }
      if (i > 0) join(par[i], i);
    }
    for (int i = 1; i < tms; i++) {
      if (dom[i] != sdm[i]) dom[i] = dom[dom[i]];
      tree[rev[i]].push_back(rev[dom[i]]);
      tree[rev[dom[i]]].push_back(rev[i]);
    }
  }
} domtree;
const int maxn = 100 + 5;
int n, m, s, t;
vector<int> adj[maxn];
int k;
int x[maxn];
int y[maxn];
vector<int> g[maxn];
int d[maxn][maxn];
vector<int> adj2[maxn];
int must[maxn][maxn];
int num[maxn];
int out[maxn];
int ptr;
void dfs(int u, int p) {
  num[u] = ptr++;
  for (int i = (0); i < (int((adj2[u]).size())); i++) {
    int v = adj2[u][i];
    if (v != p) {
      dfs(v, u);
    }
  }
  out[u] = ptr - 1;
}
int isanc(int u, int v) {
  if (num[u] == -1 || num[v] == -1) return 0;
  return num[u] <= num[v] && out[u] >= out[v];
}
void work(int u) {
  domtree.init(n, u);
  for (int v = (0); v < (n); v++) {
    for (int i = (0); i < (int((adj[v]).size())); i++) {
      int w = adj[v][i];
      if (d[u][w] == d[u][v] + 1) {
        domtree.add(v, w);
      }
    }
  }
  domtree.build();
  for (int i = (0); i < (n); i++) {
    adj2[i] = domtree.tree[i];
  }
  for (int i = (0); i < (n); i++) num[i] = out[i] = -1;
  ptr = 0, dfs(u, -1);
  for (int i = (0); i < (int((g[u]).size())); i++) {
    int ix = g[u][i];
    for (int v = (0); v < (n); v++) {
      must[ix][v] = isanc(v, y[ix]);
    }
  }
}
int dp[maxn][maxn];
void solve() {
  cin >> n >> m >> s >> t;
  s--, t--;
  for (int i = (0); i < (n); i++)
    for (int j = (0); j < (n); j++) d[i][j] = i == j ? 0 : INF;
  for (int i = (0); i < (m); i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    d[u][v] = 1;
  }
  for (int k = (0); k < (n); k++)
    for (int i = (0); i < (n); i++)
      for (int j = (0); j < (n); j++) chkmin(d[i][j], d[i][k] + d[k][j]);
  cin >> k;
  for (int i = (0); i < (k); i++) {
    cin >> x[i] >> y[i], x[i]--, y[i]--;
    g[x[i]].push_back(i);
  }
  for (int u = (0); u < (n); u++) work(u);
  for (int i = (0); i < (n); i++)
    for (int j = (0); j < (k + 1); j++) dp[i][j] = INF;
  for (int i = (0); i < (k); i++) dp[t][i] = 0;
  while (1) {
    int found = 0;
    for (int u = (0); u < (n); u++)
      for (int ix = (0); ix < (k + 1); ix++) {
        if (ix < k && u != y[ix]) {
          int tmp = 0;
          for (int v = (0); v < (n); v++)
            if (d[u][v] == 1 && d[u][v] + d[v][y[ix]] == d[u][y[ix]]) {
              chkmax(tmp, dp[v][ix]);
            }
          if (chkmin(dp[u][ix], tmp)) {
            found = 1;
          }
        }
        int tmp = INF;
        for (int i = (0); i < (k); i++)
          if (i != ix && must[i][u]) {
            chkmin(tmp, dp[u][i] + 1);
          }
        if (ix < k) {
          for (int v = (0); v < (n); v++)
            if (d[u][v] + d[v][y[ix]] == d[u][y[ix]] && must[ix][v]) {
              chkmin(tmp, dp[v][ix]);
            }
        }
        if (chkmin(dp[u][ix], tmp)) {
          found = 1;
        }
      }
    if (!found) break;
  }
  int res = dp[s][k];
  if (res == INF) res = -1;
  cout << res << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int JUDGE_ONLINE = 1;
  if (argc > 1) {
    JUDGE_ONLINE = 0;
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    JUDGE_ONLINE = 0;
    assert(freopen(argv[2], "w", stdout));
  }
  solve();
  if (!JUDGE_ONLINE) {
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  }
  return 0;
}