// This is a couple cheeses put together, to make sure we break them all in the
// same case:
//
// 1) Solve each connected component independently.
// 2) Is left or right the optimal?
// 3) Randomly find a largest independent set, assign that to 0.
//    Then find another largest independent set in the remaining graph, assign
//    that to 1.
// 4) Repeat 3 a bunch and take the best.
//
// A lot of this was vibe coded...

#include <bits/stdc++.h>
using namespace std;

class BipartiteMaximumIndependentSet {
public:
  BipartiteMaximumIndependentSet(int n_left, int n_right,
                                 const vector<pair<int, int>> &edges)
      : n_left(n_left), n_right(n_right) {
    adj.resize(n_left);
    for (const auto &edge : edges) {
      adj[edge.first].push_back(edge.second);
    }
    pair_u.assign(n_left, -1);
    pair_v.assign(n_right, -1);
    rng.seed(1567813265LL);
  }

  bool dfs(int u, vector<bool> &visited) {
    shuffle(adj[u].begin(), adj[u].end(), rng);
    for (int v : adj[u]) {
      if (!visited[v]) {
        visited[v] = true;
        if (pair_v[v] < 0 || dfs(pair_v[v], visited)) {
          pair_u[u] = v;
          pair_v[v] = u;
          return true;
        }
      }
    }
    return false;
  }

  int maximum_matching() {
    int matching_size = 0;
    bool updated = true;
    while (updated) {
      updated = false;
      vector<int> order(n_left);
      for (int i = 0; i < n_left; ++i)
        order[i] = i;
      shuffle(order.begin(), order.end(), rng);

      for (int u : order) {
        if (pair_u[u] == -1) {
          vector<bool> visited(n_right, false);
          if (dfs(u, visited)) {
            matching_size++;
            updated = true;
          }
        }
      }
    }
    return matching_size;
  }

  vector<pair<char, int>> maximum_independent_set() {
    maximum_matching();
    vector<bool> visited_u(n_left, false);
    vector<bool> visited_v(n_right, false);

    vector<int> order(n_left);
    for (int i = 0; i < n_left; ++i)
      order[i] = i;
    shuffle(order.begin(), order.end(), rng);

    for (int u : order) {
      if (pair_u[u] == -1) {
        dfs_independent_set(u, visited_u, visited_v);
      }
    }

    vector<pair<char, int>> independent_set;
    for (int u = 0; u < n_left; ++u) {
      if (visited_u[u]) {
        independent_set.push_back({'L', u});
      }
    }
    for (int v = 0; v < n_right; ++v) {
      if (!visited_v[v]) {
        independent_set.push_back({'R', v});
      }
    }
    return independent_set;
  }

private:
  int n_left, n_right;
  vector<vector<int>> adj;
  vector<int> pair_u;
  vector<int> pair_v;
  mt19937 rng;

  void dfs_independent_set(int u, vector<bool> &visited_u,
                           vector<bool> &visited_v) {
    visited_u[u] = true;
    shuffle(adj[u].begin(), adj[u].end(), rng);
    for (int v : adj[u]) {
      if (pair_u[u] != v && !visited_v[v]) {
        visited_v[v] = true;
        if (pair_v[v] != -1) {
          dfs_independent_set(pair_v[v], visited_u, visited_v);
        }
      }
    }
  }
};

struct Problem {
  int n;
  vector<pair<int, int>> edges;
  vector<pair<char, int>> useless_nodes;
};

Problem get_edges() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> orig_edges(m);
  for (int i = 0; i < m; ++i) {
    cin >> orig_edges[i].first >> orig_edges[i].second;
    orig_edges[i].first--;
    orig_edges[i].second--;
  }
  string sides;
  cin >> sides;

  vector<pair<int, int>> edges;
  for (auto &edge : orig_edges) {
    int u = edge.first;
    int v = edge.second;
    if (sides[u] == '1') {
      swap(u, v);
    }
    edges.push_back({u, v});
  }

  vector<pair<char, int>> useless_nodes;
  for (int i = 0; i < n; ++i) {
    if (sides[i] == '1') {
      useless_nodes.push_back({'L', i});
    } else {
      useless_nodes.push_back({'R', i});
    }
  }
  return {n, edges, useless_nodes};
}

int run_once(int N, vector<pair<int, int>> edges,
             const vector<pair<char, int>> &useless_nodes_const) {
  vector<pair<char, int>> useless_nodes = useless_nodes_const;
  BipartiteMaximumIndependentSet mis_zero(N, N, edges);
  vector<pair<char, int>> zeroes = mis_zero.maximum_independent_set();

  set<pair<char, int>> useless_set(useless_nodes.begin(), useless_nodes.end());
  vector<pair<char, int>> filtered_zeroes;
  for (const auto &node : zeroes) {
    if (useless_set.find(node) == useless_set.end()) {
      filtered_zeroes.push_back(node);
    }
  }
  zeroes = filtered_zeroes;

  set<pair<char, int>> zeroes_set(zeroes.begin(), zeroes.end());
  vector<pair<int, int>> remaining_edges;
  for (const auto &edge : edges) {
    if (zeroes_set.find({'L', edge.first}) == zeroes_set.end() &&
        zeroes_set.find({'R', edge.second}) == zeroes_set.end()) {
      remaining_edges.push_back(edge);
    }
  }

  BipartiteMaximumIndependentSet mis_one(N, N, remaining_edges);
  vector<pair<char, int>> ones = mis_one.maximum_independent_set();

  vector<pair<char, int>> filtered_ones;
  for (const auto &node : ones) {
    if (useless_set.find(node) == useless_set.end() &&
        zeroes_set.find(node) == zeroes_set.end()) {
      filtered_ones.push_back(node);
    }
  }

  int num_zeroes = zeroes.size();
  int num_ones = filtered_ones.size();
  int num_twos = N - num_zeroes - num_ones;

  return 1 * num_ones + 2 * num_twos;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> orig_edges(m);
  vector<vector<int>> full_adj(n);
  for (int i = 0; i < m; ++i) {
    cin >> orig_edges[i].first >> orig_edges[i].second;
    orig_edges[i].first--;
    orig_edges[i].second--;
    full_adj[orig_edges[i].first].push_back(orig_edges[i].second);
    full_adj[orig_edges[i].second].push_back(orig_edges[i].first);
  }
  string sides;
  cin >> sides;

  vector<vector<int>> components;
  vector<bool> visited(n, false);
  for (int i = 0; i < n; ++i) {
    if (!visited[i]) {
      vector<int> component;
      vector<int> q;
      q.push_back(i);
      visited[i] = true;
      int head = 0;
      while (head < q.size()) {
        int u = q[head++];
        component.push_back(u);
        for (int v : full_adj[u]) {
          if (!visited[v]) {
            visited[v] = true;
            q.push_back(v);
          }
        }
      }
      components.push_back(component);
    }
  }

  int total_best = 0;
  for (const auto &component : components) {
    int comp_n = component.size();
    if (comp_n == 0)
      continue;

    map<int, int> node_map;
    for (int i = 0; i < comp_n; ++i) {
      node_map[component[i]] = i;
    }

    vector<pair<int, int>> comp_orig_edges;
    for (const auto &edge : orig_edges) {
      if (node_map.count(edge.first)) {
        comp_orig_edges.push_back(edge);
      }
    }

    string comp_sides(comp_n, '0');
    for (int i = 0; i < comp_n; ++i) {
      comp_sides[i] = sides[component[i]];
    }

    vector<pair<int, int>> edges;
    for (auto &edge : comp_orig_edges) {
      int u = node_map[edge.first];
      int v = node_map[edge.second];
      if (comp_sides[u] == '1') {
        swap(u, v);
      }
      edges.push_back({u, v});
    }

    vector<pair<char, int>> useless_nodes;
    for (int i = 0; i < comp_n; ++i) {
      if (comp_sides[i] == '1') {
        useless_nodes.push_back({'L', i});
      } else {
        useless_nodes.push_back({'R', i});
      }
    }

    set<int> all_nodes;
    for (int i = 0; i < comp_n; ++i)
      all_nodes.insert(i);

    set<int> edge_nodes;
    for (const auto &edge : edges) {
      edge_nodes.insert(edge.first);
      edge_nodes.insert(edge.second);
    }

    set<int> isolated;
    set_difference(all_nodes.begin(), all_nodes.end(), edge_nodes.begin(),
                   edge_nodes.end(), inserter(isolated, isolated.begin()));

    set<int> left_useless, right_useless;
    for (const auto &node : useless_nodes) {
      if (node.first == 'L')
        left_useless.insert(node.second);
      else
        right_useless.insert(node.second);
    }

    set<int> left_minus_iso, right_minus_iso;
    set_difference(left_useless.begin(), left_useless.end(), isolated.begin(),
                   isolated.end(),
                   inserter(left_minus_iso, left_minus_iso.begin()));
    set_difference(right_useless.begin(), right_useless.end(), isolated.begin(),
                   isolated.end(),
                   inserter(right_minus_iso, right_minus_iso.begin()));

    int best = min(left_minus_iso.size(), right_minus_iso.size());

    for (int i = 0; i < 25; ++i) {
      best = min(best, run_once(comp_n, edges, useless_nodes));

      vector<pair<int, int>> swapped_edges;
      for (const auto &edge : edges) {
        swapped_edges.push_back({edge.second, edge.first});
      }
      edges = swapped_edges;

      vector<pair<char, int>> swapped_useless;
      for (const auto &node : useless_nodes) {
        swapped_useless.push_back(
            {(node.first == 'L' ? 'R' : 'L'), node.second});
      }
      useless_nodes = swapped_useless;
    }
    total_best += best;
  }

  cout << total_best << endl;
}