#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long a) {
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(long long a) {
  write(a);
  puts("");
}
inline void wri(long long a) {
  write(a);
  putchar(' ');
}
long long rnd() {
  unsigned long long ans = 0;
  for (int i = (int)(0); i <= (int)(4); i++) ans = ans << 15 ^ rand();
  return ans % ((unsigned long long)1 << 63);
}
const int K = 22, M = 1 << 20 | 3, inf = 1e9, N = 1000005;
char s[K], t[K];
int n, m, k, dp[K][M], p[K], ZT[N];
int main() {
  n = read();
  m = read();
  k = read();
  scanf("%s%s", s, t);
  for (int i = (int)(0); i <= (int)(k - 1); i++) {
    s[i] -= '0';
    t[i] -= '0';
  }
  for (int i = (int)(0); i <= (int)(k); i++)
    for (int j = (int)(0); j <= (int)((1 << k) - 1); j++) dp[i][j] = inf;
  for (int i = (int)(0); i <= (int)(k - 1); i++) p[i] = i;
  for (int i = (int)(1); i <= (int)(n); i++) {
    int x = read() - 1, y = read() - 1;
    int zt = 0;
    for (int j = (int)(0); j <= (int)(k - 1); j++) {
      zt |= s[p[j]] << j;
    }
    dp[0][zt] = min(dp[0][zt], i - 1);
    for (int j = (int)(0); j <= (int)(k - 1); j++)
      if (p[j] == x || p[j] == y) p[j] ^= x ^ y;
    for (int j = (int)(0); j <= (int)(k - 1); j++) {
      ZT[i] |= t[p[j]] << j;
    }
  }
  for (int i = (int)(1); i <= (int)(k); i++)
    for (int j = (int)(0); j <= (int)((1 << k) - 1); j++)
      for (int o = (int)(0); o <= (int)(k - 1); o++) {
        dp[i][j] = min(dp[i][j], dp[i - 1][j ^ (1 << o)]);
      }
  int ans = inf;
  for (int i = (int)(1); i <= (int)(n); i++) {
    for (int j = (int)(0); j <= (int)(k); j++)
      if (i - dp[j][ZT[i]] >= m) ans = min(ans, j);
  }
  writeln(k - ans);
  for (int i = (int)(1); i <= (int)(n); i++) {
    if (i - dp[ans][ZT[i]] >= m) {
      cout << dp[ans][ZT[i]] + 1 << " " << i << endl;
      return 0;
    }
  }
}
