#include <bits/stdc++.h>
using namespace std;
int const N = 1000000, B = 20, inf = 1e9;
int n, m, k, dp[B + 1][1 << B], p[B];
pair<int, int> op[N];
string a, b, t;
inline void up(int &x, int y) {
  if (y < x) x = y;
}
inline int tr(string const &s) {
  int an = 0;
  for (int i = 0; i < (int)(s.size()); ++i) an = an << 1 | s[i] == '1';
  return an;
}
int pr(string const &s) {
  for (int i = 0; i < (int)(k); ++i) t[p[i]] = s[i];
  return tr(t);
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  cin >> a >> b;
  t.resize(a.size(), '0');
  for (int i = 0; i < (int)(k + 1); ++i)
    for (int j = 0; j < (int)(1 << k); ++j) dp[i][j] = inf;
  for (int i = 0; i < (int)(k); ++i) p[i] = i;
  for (int i = 0; i < (int)(n); ++i) {
    up(dp[0][pr(a)], i + 1);
    scanf("%d%d", &op[i].first, &op[i].second);
    --op[i].first;
    --op[i].second;
    swap(p[op[i].first], p[op[i].second]);
  }
  for (int i = 0; i < (int)(k); ++i)
    for (int j = 0; j < (int)(1 << k); ++j)
      if (dp[i][j] < inf)
        for (int w = 0; w < (int)(k); ++w)
          if (!(j >> w & 1)) up(dp[i + 1][j | 1 << w], dp[i][j]);
  for (int i = 0; i < (int)(k); ++i)
    for (int j = 0; j < (int)(1 << k); ++j)
      if (dp[i][j] < inf)
        for (int w = 0; w < (int)(k); ++w)
          if (j >> w & 1) up(dp[i + 1][j ^ 1 << w], dp[i][j]);
  int an = inf, l = 0, r = 0;
  for (int i = 0; i < (int)(k); ++i) p[i] = i;
  for (int i = 0; i < (int)(n); ++i) {
    swap(p[op[i].first], p[op[i].second]);
    int tra = pr(b);
    for (int j = 0; j < (int)(k + 1); ++j) {
      int t = dp[j][tra];
      if (i + 2 - t >= m && j < an) {
        an = j;
        l = t;
        r = i + 1;
      }
    }
  }
  printf("%d\n%d %d\n", k - an, l, r);
}
