#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
template <class T>
using V = vector<T>;
template <class T>
using VV = vector<vector<T>>;
template <class T, class U>
void chmax(T& x, U y) {
  if (x < y) x = y;
}
template <class T, class U>
void chmin(T& x, U y) {
  if (y < x) x = y;
}
template <class T>
void mkuni(V<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
template <class S, class T>
ostream& operator<<(ostream& o, const pair<S, T>& p) {
  return o << "(" << p.first << "," << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& vc) {
  o << "{";
  for (const T& v : vc) o << v << ",";
  o << "}";
  return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int M, D, N;
  cin >> M >> D >> N;
  int S = 0, T = 0;
  {
    string s;
    cin >> s;
    for (int i = 0; i < int(N); i++)
      if (s[i] == '1') S |= 1 << i;
    cin >> s;
    for (int i = 0; i < int(N); i++)
      if (s[i] == '1') T |= 1 << i;
  }
  using P = pair<int, int>;
  V<P> sw;
  for (int i = 0; i < int(M); i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    sw.emplace_back(x, y);
  }
  V<int> A(M + 1), B(M + 1);
  {
    A[M] = S, B[M] = T;
    V<int> p(N);
    iota(p.begin(), p.end(), 0);
    for (int i = int(M) - 1; i >= 0; i--) {
      swap(p[sw[i].first], p[sw[i].second]);
      for (int j = 0; j < int(N); j++) {
        if (S & 1 << j) A[i] |= 1 << p[j];
        if (T & 1 << j) B[i] |= 1 << p[j];
      }
    }
  }
  int inf = 1e8;
  V<int> l(1 << N, inf), r(1 << N, -inf);
  for (int i = 0; i < int(M + 1); i++) {
    chmin(l[A[i]], i);
    chmax(r[B[i]], i);
  }
  for (int i = 0; i < int(N); i++)
    for (int j = 0; j < int(1 << N); j++)
      if (j & 1 << i) {
        chmin(l[j ^ (1 << i)], l[j]);
        chmax(r[j ^ (1 << i)], r[j]);
      }
  int ans = -1, L = 0, R = 0;
  for (int s = 0; s < int(1 << N); s++) {
    if (r[s] - l[s] >= D) {
      int score = __builtin_popcount(s);
      if (ans < score) {
        ans = score, L = l[s], R = r[s];
      }
    }
  }
  ans = N - __builtin_popcount(S) - __builtin_popcount(T) + 2 * ans;
  cout << ans << endl;
  cout << L + 1 << " " << R << endl;
}
