#include <bits/stdc++.h>
std::pair<int, int> a[1048576];
std::pair<int, int> lu[(1 << 20)];
int mps[32], mpd[32];
std::pair<int, int> que[(1 << 20)];
int nq, cq;
char ss[32], second[32];
void bfs(int rt, int x, int m) {
  nq = cq = 0;
  if (lu[rt].first <= 0) return;
  lu[rt] = {0, x};
  que[nq++] = {rt, 0};
  while (cq != nq) {
    int u, cu;
    std::tie(u, cu) = que[cq++];
    for (int i = 1 << m - 1; i; i >>= 1) {
      int v = u ^ i, cv = cu + 1;
      if (lu[v].first <= cv) continue;
      lu[v] = {cv, x};
      que[nq++] = {v, cv};
    }
  }
}
int main() {
  int n, x, m;
  scanf("%d%d%d%s%s", &n, &x, &m, ss, second);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &a[i].first, &a[i].second), --a[i].first, --a[i].second;
  for (int i = 0; i < m; ++i) mpd[i] = mps[i] = i;
  for (int i = 0; i < 1 << m; ++i) lu[i] = {32, -1};
  for (int i = 0; i < x; ++i) std::swap(mpd[a[i].first], mpd[a[i].second]);
  int ans = 32, l = -1, r = -1;
  for (int i = x, j = 0; i <= n; std::swap(mpd[a[i].first], mpd[a[i].second]),
           ++i, std::swap(mps[a[j].first], mps[a[j].second]), ++j) {
    int ts = 0, td = 0;
    for (int k = 0; k < m; ++k) ts |= ss[k] - '0' << mps[k];
    for (int k = 0; k < m; ++k) td |= second[k] - '0' << mpd[k];
    0;
    bfs(ts, j, m);
    if (lu[td].first < ans) std::tie(ans, l) = lu[td], r = i;
  }
  printf("%d\n%d %d\n", m - ans, l + 1, r);
  return 0;
}
