#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define ll long long #define pi pair<int,int> #define vi vector<int> #define pb push_back #define all(a) a.begin(),a.end() const int mxn = 15e4+1, mxa = 2e7; int root[mxn], pl[mxa], pr[mxa], node = 0; bool st[mxa]; int edge[200001][2]; int cola[mxn], colb[mxn], par[mxn]; int n,m; vector<array<int,3>> history; vector<pi> edges[1<<19]; vector<int> qu[mxn]; // (~persistent) dynamic segment tree int update1(int cur, int l, int r, int k){ if(!cur) cur = ++node; if(l==r){ st[cur] = 1; return cur;} int m = (l+r)>>1; if(k <= m) pl[cur] = update1(pl[cur],l,m,k); else pr[cur] = update1(pr[cur],m+1,r,k); return cur; } int merge1(int cur1, int cur2, int l, int r){ if(!cur1) return cur2; if(!cur2) return cur1; int cur = ++node, m = (l+r)>>1; if(l==r){ st[cur] = st[cur1] || st[cur2]; return cur; } pl[cur] = merge1(pl[cur1],pl[cur2],l,m); pr[cur] = merge1(pr[cur1],pr[cur2],m+1,r); return cur; } bool query(int cur, int l, int r, int k){ if(!cur) return 0; if(l==r) return st[cur]; int m = (l+r)>>1; if(k <= m) return query(pl[cur],l,m,k); else return query(pr[cur],m+1,r,k); } // DSU-rollback int find(int u){ if(par[u]<0) return u; return find(par[u]); } bool merge(int u, int v){ u = find(u), v = find(v); if(u==v) return false; if(par[u]>par[v]) swap(u,v); history.push_back({u,par[u],root[u]}); history.push_back({v,par[v],root[v]}); par[u] += par[v]; par[v] = u; root[u] = merge1(root[u],root[v],1,n); return true; } // Offline connectivity void add_edge(int i, int l, int r, int s, int e, pi ed){ if(r < s || l > e) return; if(s <= l && r <= e){ edges[i].push_back(ed); return; } int m = (l+r)>>1; add_edge(i<<1,l,m,s,e,ed); add_edge(i<<1|1,m+1,r,s,e,ed); } bool dfs(int i, int l, int r){ int snapshot = history.size(); for(auto [u,v] : edges[i]) merge(u,v); if(l==r){ for(auto u : qu[l]){ if(!query(root[find(u)],1,n,l)) return true; } }else{ int m = (l+r)>>1; if(dfs(i<<1,l,m)) return true; if(dfs(i<<1|1,m+1,r)) return true; } for(; history.size() > snapshot;){ auto [u,a,b] = history.back(); par[u] = a; root[u] = b; history.pop_back(); } return false; } void clear(int i, int l, int r){ edges[i].clear(); if(l==r) return; int m = (l+r)>>1; clear(i<<1,l,m); clear(i<<1|1,m+1,r); } void solve(){ cin >> n >> m; fill(pl+1,pl+node+1,0); fill(pr+1,pr+node+1,0); fill(st+1,st+node+1,false); fill(par+1,par+n+1,-1); node = 0; history.clear(); for(int i = 1; i <= n; i++) cin >> cola[i]; for(int i = 1; i <= n; i++){ cin >> colb[i]; qu[i].clear(); } for(int i = 1; i <= m; i++) cin >> edge[i][0] >> edge[i][1]; for(int i = 1; i <= n; i++){ if(cola[i] < colb[i]){ cout << "0\n"; return; } root[i] = update1(0,1,n,cola[i]); qu[colb[i]].push_back(i); } for(int i = 1; i <= n; i++){ int l = max(colb[edge[i][0]],colb[edge[i][1]]); int r = min(cola[edge[i][0]],cola[edge[i][1]]); if(l <= r) add_edge(1,1,n,l,r,{edge[i][0],edge[i][1]}); } if(dfs(1,1,n)) cout << "0\n"; else cout << "1\n"; } signed main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; cin >> t; for(int i = 0; i < t; i++){solve();} }