#import<bits/stdc++.h>
#define c(a,b)(a=a>b?a:b)
long n,m,h[1<<17],G[1<<17],i,u,v,p[1<<18],q,x;main(){for(;std::cin>>v;)n?m?i<n?h[i++]=v:i++-n&1?h[--u]<h[--v]?:u^=v^=u^=v,G[i+~n>>1]=h[u]*n*n+u*n+v:u=v:m=v:n=v;std::sort(G,G+m);p[0]=p[2*n-1]=n+1;for(i=0;x=G[i++];c(q,c(p[v],p[u]+1)+c(p[v+n],p[u+n]+1)-2*n))u=x/n%n,v=x%n;printf("%d\n",q-1);}