#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void cmin(T &a, T b) {
  ((a > b) && (a = b));
}
int cmax(int &a, int b) { return a < b ? a = b, 1 : 0; }
char IO;
template <class T = int>
T rd() {
  T s = 0;
  int f = 0;
  while (!isdigit(IO = getchar())) f |= IO == '-';
  do s = (s << 1) + (s << 3) + (IO ^ '0');
  while (isdigit(IO = getchar()));
  return f ? -s : s;
}
const int N = 1e6 + 10, INF = 1e9 + 10;
int n, m, k, T;
int s[N], t[N];
int F[1 << 20], G[1 << 20];
int p[N], a[N], b[N];
int main() {
  n = rd(), m = rd(), k = rd();
  for (int i = 0, iend = k - 1; i <= iend; ++i) scanf("%1d", s + i);
  for (int i = 0, iend = k - 1; i <= iend; ++i) scanf("%1d", t + i);
  for (int i = 0, iend = k - 1; i <= iend; ++i) p[i] = i;
  memset(F, 63, sizeof F), memset(G, -63, sizeof G);
  int S = 0;
  for (int i = 0, iend = k - 1; i <= iend; ++i) S |= s[i] << i;
  F[S] = 0;
  for (int i = 1, iend = n; i <= iend; ++i) {
    int x = rd() - 1, y = rd() - 1;
    for (int j = 0, jend = k - 1; j <= jend; ++j)
      if (p[j] == x) {
        x = j;
        break;
      }
    for (int j = 0, jend = k - 1; j <= jend; ++j)
      if (p[j] == y) {
        y = j;
        break;
      }
    swap(p[x], p[y]);
    int S = 0, T = 0;
    for (int j = 0, jend = k - 1; j <= jend; ++j) {
      S |= s[p[j]] << j;
      T |= t[p[j]] << j;
    }
    cmin(F[S], i), G[T] = i;
  }
  int ans = 0, l = 1, r = n, c1 = 0, c2 = 0;
  for (int i = 0, iend = k - 1; i <= iend; ++i) c1 += s[i], c2 += t[i];
  for (int S = (1 << k) - 1, Send = 0; S >= Send; --S) {
    if (G[S] - F[S] >= m)
      if (cmax(ans, k - (c1 + c2 - 2 * __builtin_popcount(S))))
        l = F[S] + 1, r = G[S];
    for (int i = 0, iend = k - 1; i <= iend; ++i)
      if (S & (1 << i)) {
        cmin(F[S ^ (1 << i)], F[S]);
        cmax(G[S ^ (1 << i)], G[S]);
      }
  }
  printf("%d\n%d %d\n", ans, l, r);
}
