/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kein Yukiyoshi
 */

#include "bits/stdc++.h"
#define int long long
#define rep(i, n)           for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b)        for (int i = (int)(a); i < (int)(b); i++)
#define FOR(i, a)           for (auto &i : a)
#define ALL(obj)            begin(obj), end(obj)
#define MAX(x)              *max_element(ALL(x))
#define MIN(x)              *min_element(ALL(x))
#define SUM(x)              accumulate(ALL(x), 0LL)
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))

using namespace std;
const int MOD    = (int)(1e9 + 7);
const int INF    = (int)(1e13 + 7);
const double EPS = 1e-14;
const double PI  = acos(-1);

int CEIL(int a, int b) { return (a >= 0 ? (a + (b - 1)) / b : (a - (b - 1)) / b); } //ceil() for int
int mod(int a, int b) { return a >= 0 ? a % b : a - (b * CEIL(a, b)); }             //always return positive num
int bpm(int a, int b) {                                                             //return x^y in order(log(y))
  int res = 1;
  for (a %= MOD; b; a = a * a % MOD, b >>= 1)
    if (b & 1) res = res * a % MOD;
  return res;
}

struct UnionFind {
  vector<int> d;
  UnionFind(int n = 0) : d(n, -1) {} //0からn-1
  int find(int x) { return (d[x] < 0 ? x : d[x] = find(d[x])); }
  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -d[find(x)]; }
};

class BValues {
public:
  static void solve(istream &cin, ostream &cout) {
    int N, M;
    cin >> N >> M;
    vector<int> a(N);
    vector<int> b(N);
    rep(i, N) cin >> a[i];
    rep(i, N) cin >> b[i];
    if (SUM(a) != SUM(b)) {
      cout << "No" << endl;
      return;
    }
    UnionFind temp(N + 100);
    rep(i, M) {
      int c, d;
      cin >> c >> d;
      temp.unite(c, d);
    }
    map<int, pair<int, int>> check;
    REP(i, 1, N + 1) {
      check[temp.find(i)].first += a[i-1];
      check[temp.find(i)].second += b[i-1];
    }
    FOR(i, check) {
      if (i.second.second != i.second.first) {
        cout << "No" << endl;
        return;
      }
    }
    cout << "Yes" << endl;
  }
};


signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
  BValues solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define data data123

const int N = 1005;

vector<int> G[N*N];

int n, m;

int pos(int i, int j) {
    return (i-1)*n+j;
}

vector<pii> data[N*N];
bool vis[N*N];

void solve() {
    scanf("%d%d", &n, &m);
    char ch[5];
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d%s", &u, &v, ch);
        data[u].push_back(pii(v, ch[0]-'a'));
        data[v].push_back(pii(u, ch[0]-'a'));
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (auto v1: data[i]) {
                for (auto v2: data[j]) {
                    if (v1.second == v2.second) {
                        G[pos(i, j)].push_back(pos(v1.first, v2.first));
                    }
                }
            }
        }
    }

    queue<pii> que;
    for (int i = 1; i <= n; i++) {
        que.push(pii(pos(i, i), 0));
        vis[pos(i, i)] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (auto v: data[i]) {
            que.push(pii(pos(i, v.first), 1));
            vis[pos(i, v.first)] = 1;
        }
    }
    while (!que.empty()) {
        pii t = que.front(); que.pop();
        int u = t.first;
        int x = ((u % n == 0) ? (u/n) : (u/n+1));
        int y = ((u % n == 0) ? n : (u%n));
        if ((x == 1 && y == n) || (x == n && y == 1)) {
            printf("%d\n", t.second);
            return;
        }
        for (auto v: G[u]) {
            if (!vis[v]) que.push(pii(v, t.second+2)), vis[v] = 1;
        }
    }
    printf("-1\n");

}

int main(){

    solve();
    return 0;
}