旅游胜地

显然可以二分最小值。

然后对于一个点取某个值的时候，对于相邻的点我们有能选或者不能一起选，直接2-SAT即可。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,a[N],b[N],dfn[N],low[N],cnt,vis[N],scc[N],ux[N],vx[N],co;
vector<int> g[N]; stack<int> s;
void Tarjan(int x){low[x]=dfn[x]=++cnt; vis[x]=1; s.push(x);for(int to:g[x]){if(!dfn[to]) Tarjan(to),low[x]=min(low[x],low[to]);else if(vis[to]) low[x]=min(low[x],dfn[to]);}if(low[x]==dfn[x]){int u; co++;do{u=s.top(); s.pop(); vis[u]=0; scc[u]=co;}while(u!=x);}
}
inline int check(int mid){cnt=co=0;for(int i=1;i<=n*2;i++) dfn[i]=low[i]=scc[i]=0,g[i].clear();for(int i=1;i<=m;i++){int x=ux[i],y=vx[i];if(abs(a[x]-a[y])>mid) g[x].push_back(y+n),g[y].push_back(x+n);if(abs(a[x]-b[y])>mid) g[x].push_back(y),g[y+n].push_back(x+n);if(abs(b[x]-a[y])>mid) g[x+n].push_back(y+n),g[y].push_back(x);if(abs(b[x]-b[y])>mid) g[x+n].push_back(y),g[y+n].push_back(x);}for(int i=1;i<=n*2;i++) if(!dfn[i]) Tarjan(i);for(int i=1;i<=n;i++) if(scc[i]==scc[i+n]) return 0;return 1;
}
signed main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=m;i++) cin>>ux[i]>>vx[i];int l=0,r=1e9;while(l<r){int mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;}cout<<l;return 0;
}