#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; typedef __uint128_t i128; #define ppc __builtin_popcount const int maxn=1e6+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,k; int S1,S2; int a[maxn],b[maxn]; int f[1<<20],g[1<<20],p[maxn]; int trans(){ string s;cin>>s;reverse(s.begin(),s.end()); int res=0;for(char ch:s)res=res*2+ch-'0'; return res; } void slv(){ n=read(),m=read(),k=read(); S1=trans();S2=trans(); up(i,1,n)a[i]=read(),b[i]=read(),a[i]--,b[i]--; memset(f,0x3f,sizeof(f)); up(i,0,k-1)p[i]=i; f[S1]=n+1;int x=S1; down(i,n,1){ int &A=p[a[i]],&B=p[b[i]];swap(A,B); int w1=(x>>A)&1,w2=(x>>B)&1; if(w1)x^=(1<<A),x^=(1<<B);if(w2)x^=(1<<A),x^=(1<<B); f[x]=min(f[x],i); } up(i,0,k-1)p[i]=i; g[S2]=n+1;x=S2;down(i,n,1){ int &A=p[a[i]],&B=p[b[i]];swap(A,B); int w1=(x>>A)&1,w2=(x>>B)&1; if(w1)x^=(1<<A),x^=(1<<B);if(w2)x^=(1<<A),x^=(1<<B); g[x]=max(g[x],i); } up(i,0,k-1)up(j,0,(1<<k)-1)if(!((j>>i)&1))f[j]=min(f[j],f[j+(1<<i)]),g[j]=max(g[j],g[j+(1<<i)]); int mx=-1; int L=0,R=0; up(i,0,(1<<k)-1)if(g[i]-f[i]>=m&&ppc(i)>mx)mx=ppc(i),L=f[i],R=g[i]; mx<<=1;mx+=k;mx-=ppc(S1)+ppc(S2); cout<<mx<<endl<<L<<" "<<R-1<<endl; } int main(){ //freopen("game.in","r",stdin); //freopen("game.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }