#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    int H, W, N, M;
    cin >> H >> W >> N >> M;
    int mat[H][W];
    rep(i, H) rep(j, W) {
        mat[i][j] = 0;
    }
    vector<P> light;
    rep(i, N) {
        int p1, p2;
        cin >> p1 >> p2;
        light.push_back((P){p1-1, p2-1});
    }
    rep(i, M) {
        int p1, p2;
        cin >> p1 >> p2;
        mat[p1-1][p2-1] = -1;
    }
    int count = 0;
    for(auto p : light) {
        if(mat[p.first][p.second] == 0) {
            count++;
            mat[p.first][p.second] = 1;
            int i = 1;
            while(p.first+i < H && mat[p.first+i][p.second] != -1) {
                mat[p.first+i][p.second] = 1;
                count++;
                i++;
            }
            i = 1;
            while(p.first-i >= 0 && mat[p.first-i][p.second] != -1) {
                mat[p.first-i][p.second] = 1;
                count++;
                i++;
            }
        }
    }
    for(auto p : light) {
        if(mat[p.first][p.second] == 2) continue;
        int i = 1;
        while(p.second+i < W && mat[p.first][p.second+i] != -1) {
            if(mat[p.first][p.second+i] == 0) count++;
            mat[p.first][p.second+i] = 2;
            i++;
        }
        i = 1;
        while(p.second-i >= 0 && mat[p.first][p.second-i] != -1) {
            if(mat[p.first][p.second-i] == 0) count++;
            mat[p.first][p.second-i] = 2;
            i++;
        }
    }
    cout << count << endl;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

struct Edge {
  ll to;
  char c;
  Edge(ll to, char c) : to(to), c(c) {}
};

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  ll n, m;
  cin >> n >> m;
  vector<vector<Edge>> to(n);
  REP(i, m) {
    ll a, b;
    char c;
    cin >> a >> b >> c;
    a--, b--;
    to[a].push_back(Edge(b, c));
    to[b].push_back(Edge(a, c));
  }
  const ll INF = 1e18;
  vector<vector<ll>> dp(n, vector<ll>(n, INF));
  queue<P> q;
  REP(i, n) {
    dp[i][i] = 0;
    q.push({i, i});
  }
  REP(i, n) {
    for (Edge e : to[i]) {
      ll nv = e.to;
      chmin(dp[i][nv], 1LL);
      q.push({i, nv});
    }
  }

  while (!q.empty()) {
    P p = q.front();
    q.pop();
    ll a = p.first, b = p.second;
    for (Edge e1 : to[a]) {
      for (Edge e2 : to[b]) {
        if (e1.c == e2.c) {
          ll bef = dp[e1.to][e2.to], aft = dp[a][b] + 2;
          if (bef > aft) {
            dp[e1.to][e2.to] = aft;
            q.push({e1.to, e2.to});
          }
        }
      }
    }
  }

  ll ans = dp[0][n - 1];
  if (ans == INF) {
    ans = -1;
  }
  cout << ans << endl;
}