#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = 1 << 20, INF = 0x3f3f3f3f;
int n, m, k, a, b, x, y;
int dp[2][M + 5], p[N + 5], tmp[M + 5];
char s[N + 5], t[N + 5];
void g(int &x, int &y) {
  x = y = 0;
  for (int j = 0; j < k; ++j) {
    if (s[j] == '1') x |= (1 << p[j]);
    if (t[j] == '1') y |= (1 << p[j]);
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  scanf("%s%s", s, t);
  for (int i = 0; i < k; ++i) p[i] = i;
  memset(dp[0], INF, sizeof dp[0]);
  memset(dp[1], 0, sizeof dp[1]);
  g(x, y);
  dp[0][x] = 0;
  dp[1][y] = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &a, &b);
    a--;
    b--;
    swap(p[a], p[b]);
    g(x, y);
    dp[0][x] = min(dp[0][x], i);
    dp[1][y] = max(dp[1][y], i);
  }
  for (int c = 0; c <= k; ++c) {
    for (int i = 0; i < (1 << k); ++i) {
      if (dp[1][i] - dp[0][i] >= m) {
        printf("%d\n", k - c);
        printf("%d %d", dp[0][i] + 1, dp[1][i]);
        return 0;
      }
    }
    for (int i = 0; i < (1 << k); ++i) {
      tmp[i] = dp[0][i];
      for (int j = 0; j < k; ++j) tmp[i] = min(tmp[i], dp[0][i ^ (1 << j)]);
    }
    for (int i = 0; i < (1 << k); ++i) dp[0][i] = tmp[i];
  }
  return 0;
}
