#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 20) + 7;
int n, m, k, A[N], B[N], g[N], dp[N], dq[N], ds[N];
char s1[N], s2[N], s3[N];
inline int gets1() {
  int x = 0;
  for (int i = 0; i < k; i++) x |= ((s1[i + 1] - '0') << i);
  return x;
}
inline int gets2() {
  int x = 0;
  for (int i = 0; i < k; i++) x |= ((s2[i + 1] - '0') << i);
  return x;
}
inline int gets3() {
  int x = 0;
  for (int i = 0; i < k; i++) x |= ((s3[i + 1] - '0') << i);
  return x;
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  scanf("%s%s", s2 + 1, s1 + 1);
  for (int i = 0; i < (1 << k); i++) dp[i] = 1919810, dq[i] = 0;
  for (int i = 1; i <= n; i++) scanf("%d%d", &A[i], &B[i]);
  for (int i = 1; i <= k; i++) g[i] = i;
  for (int i = n; i >= 1; i--) {
    for (int i = 1; i <= k; i++) s3[i] = s1[g[i]];
    dq[gets3()] = max(dq[gets3()], i);
    int x, y;
    for (int j = 1; j <= k; j++) {
      if (g[j] == A[i]) x = j;
      if (g[j] == B[i]) y = j;
    }
    swap(g[x], g[y]);
    for (int i = 1; i <= k; i++) s3[i] = s2[g[i]];
    dp[gets3()] = min(dp[gets3()], i);
  }
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j < (1 << k); j++) {
      if (dq[j] - dp[j] + 1 >= m) {
        cout << k - i << endl;
        cout << dp[j] << " " << dq[j] << endl;
        return 0;
      }
      ds[j] = dp[j];
    }
    for (int j = 0; j < (1 << k); j++)
      for (int x = 0; x < k; x++)
        ds[j ^ (1 << x)] = min(ds[j ^ (1 << x)], dp[j]);
    for (int j = 0; j < (1 << k); j++) dp[j] = ds[j];
  }
  return 0;
}
