#include <bits/stdc++.h>
using namespace std;
int n, m, K, s[25], t[25];
int x[1000005], y[1000005], ans = -1, L = 0, R = 0;
int build(int *bs, int *per) {
  int S = 0;
  for (int i = 0; i < K; i++) S |= bs[per[i]] << i;
  return S;
}
int per[25];
int mn[1100000], mx[1100000];
int main() {
  scanf("%d%d%d", &n, &m, &K);
  int coe = K;
  memset(mn, 0x3f, sizeof(mn));
  memset(mx, -0x3f, sizeof(mx));
  for (int i = 0, x; i < K; i++) scanf("%1d", s + i), coe -= s[i];
  for (int i = 0, x; i < K; i++) scanf("%1d", t + i), coe -= t[i];
  for (int i = 1; i <= n; i++) scanf("%d%d", x + i, y + i), x[i]--, y[i]--;
  for (int i = 0; i < K; i++) per[i] = i;
  for (int i = n; i; i--) {
    int T = build(t, per);
    mx[T] = max(mx[T], i + 1);
    for (int j = 0; j < K; j++)
      if (per[j] == x[i])
        per[j] = y[i];
      else if (per[j] == y[i])
        per[j] = x[i];
    int S = build(s, per);
    mn[S] = i;
  }
  for (int i = 1; i < (1 << K); i <<= 1)
    for (int j = 0; j < (1 << K); j++)
      if (i & j) mn[i ^ j] = min(mn[i ^ j], mn[j]);
  for (int i = 1; i < (1 << K); i <<= 1)
    for (int j = 0; j < (1 << K); j++)
      if (i & j) mx[i ^ j] = max(mx[i ^ j], mx[j]);
  for (int i = 0; i < (1 << K); i++)
    if (mx[i] - mn[i] >= m) {
      int res = (__builtin_popcount(i) << 1) + coe;
      if (res > ans) ans = res, L = mn[i], R = mx[i] - 1;
    }
  printf("%d\n%d %d\n", ans, L, R);
}
