Một vài nhận xét ban đầu:

• Giá trị của ~A_i~ không bao giờ tăng do operation là gán ~\min~.

• Nếu ban đầu, ~A_i < B_i~ thì chắc chắn ta không thể biến đổi.

• Một cách biến đổi sẽ không bao giờ biến ~A_i < B_i~.

Ta có:

~A_v~ có thể được biến đổi thành ~B_v = c~ khi và chỉ khi có một đường đi từ ~u~ đến ~v~, với ~A_u = c~ và với các đỉnh ~w~ trên đường đi đó thỏa mãn ~A_w \geq c \geq B_w~.

Chứng minh:

• Nếu ~A_w < c~, thì việc gán sẽ không lấy giá trị ~c~, mà sẽ lấy giá trị ~A_w~.

• Nếu ~B_w > c~, thì việc gán sẽ làm cho ~A_w < B_w~, vi phạm một nhận xét ở trên.

Từ nhận xét trên, ta có được một nhận xét quan trọng của thuật toán. Nếu muốn biến đổi định từ ~A_i~ thành ~B_i = c~, ta sẽ phải biến một số đỉnh ~w~ từ ~A_w~ thành ~A_w'~ bé hơn, từ đó làm việc thỏa mãn khó hơn. Vì thế, thay vì xét đỉnh, nếu xét ~c~ giảm dần, ~A_w~ sẽ sẽ có ~A_w := c~ luôn và vì thế, khi ta xét giá trị tiếp theo, việc gán sẽ không có ý nghĩa nữa.

Subtask 1:

Ta thấy đồ thị là một loại cây. Gọi gốc cây là ~r~. Ta thấy, khi làm thỏa một đỉnh lá ~u~, thì ta chỉ cần xét 3 trường hợp:

• ~B_u = A_u~: Không cần làm gì.

• ~B_u = A_r~: Truyền giá trị từ ~r~ đến đỉnh ~u~.

• ~B_u = A_v~: Truyền giá trị từ ~v~ đến ~r~, rồi từ ~r~ đến ~u~.

Dù vậy, việc kiểm tra đỉnh gốc có thỏa hay không có thể hơi lằn nhằn. Nếu ta kiểm tra các đỉnh lá trước rồi mới kiểm tra gốc, thì ta không cần xử lý trường hợp đặc biệt.

Subtask 2:

Khi đồ thị là đường thẳng, ta xem nó như một mảng. Khi đó, với mọi đỉnh ~i~, ta xét đỉnh ~l~ lớn nhất bên trái có cùng giá trị, rồi xét hai điều kiện sau:

• ~m_{in}(A_l \to i) \geq B_i~: Khi đó, ta có thể truyền giá trị từ ~l~ đến ~i~.

• ~m_{ax}(B_l \to i) \leq B_i~: Khi ta truyền giá trị từ ~l~ đến ~i~, thì ta không làm thay đổi các giá trị khác không thể thỏa mãn.

Ta sử dụng RMQ (Range Minimum Query) để kiểm tra hai điều kiện trên và làm tương tự với bên phải.

Subtask 3:

Ta thấy, với mọi đỉnh ~u~, thì có không quá một đỉnh ~v~ mà ~B_u = A_v~. Vì thế, ta có thể kiểm tra như Subtask 2 và kết hợp binary lifting cùng LCA (Lowest Common Ancestor) để kiểm tra nhanh. Subtask 4:

Ta thấy ~N \times M~ bé, nên ta có thể sử dụng ~N~ pha DFS và sử dụng nhận xét đầu bài để kiểm tra trong ~O(N \times M)~.

Subtask 5:

Gọi tập đỉnh thỏa mãn ~A_u \geq c \geq B_u~ là ~V_c~ và tập cạnh ~E_c~ là các cạnh có hai đầu đều có trong ~V_c~. Khi đó, với ~c~, ta chỉ cần biết rằng với mọi đỉnh ~u~ có ~B_u = c~, thì có đỉnh ~v~ mà ~A_v = c~ nào có thể đến được ~u~ hay không. Khi đó, ta dùng DSU.

Dù vậy, việc tính lại DSU cho từng ~c~ sẽ rất lâu, nên ta xem rằng khi ta đi từ ~c~ đến ~d~ nhỏ hơn thì ~V~ và ~E~ thay đổi như thế nào:

• Nếu ~A_u = d~, thì đỉnh đó được thêm vào ~V~.

• Nếu ~B_u = c~, thì đỉnh đó được loại khỏi ~V~.

Khi đó, ta chuyển bài toán lại thành bài toán Offline Dynamic Connectivity. Bài toán này có hai cách giải với ràng buộc thời gian và không gian:

• DSU Rollback trong ~O(M \times \log_2 (N))~.

• Chia căn trong ~O(\alpha(N) \times M \times M)~.

DSU Rollback mình sẽ không bàn ở đây. Nhưng mình sẽ nói qua thuật toán chia căn:

Ta gọi một block của ta là khoảng ~[c, d]~ sao cho từ ~c~ đến ~d~ có ~sqr(M)~ cạnh được thêm vào và xóa đi. Khi đó, ta xét các block, ta dựng trước một cấu hình DSU dùng cho cả block. Khi xét cạnh ~e~ trong khoảng ~[c, d]~, ta sẽ xét thêm các cạnh mà có đóng góp cho ~e~ rồi truy vấn. Cuối cùng, ta xử lý với block tiếp theo giảm dần.

Phân tích thời gian chạy: Có không quá ~M~ block, mỗi block cần thời gian xây dựng là ~O(M \times \alpha(M))~. Với mỗi ~c~, ta chỉ trả lời trong ~O(\alpha(M) \times M)~. Vì thế, độ phức tạp sẽ là ~O(\alpha(M) \times (N + M)\times \sqrt{N})~

#include<bits/stdc++.h> //runtime: <500ms
#define ll int
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname "ARTSCHOOL"
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
ll n,m;
struct save{
    ll u,szu,v,szv;
};
vector<save> st;
vector<pair<ll,ll>>  segtree[600001];
vector<ll> colors[150001],need[150001];
ll par[150001];
ll sz[150001];
ll a[150001];
ll b[150001];
ll check[150001];
ll ans;
ll find_par(ll u){
    return (par[u]==u ? u : find_par(par[u]));
}
inline bool uni(ll u,ll v){
    u=find_par(u);
    v=find_par(v);
    if(u==v) return 0;
    if(sz[u]>sz[v]) swap(u,v);
    st.push_back({u,sz[u],v,sz[v]});
    par[u]=v;
    sz[v]+=sz[u];
    return 1;
}
inline void rollback(){
    if(st.size()==0) return ;
    save c=st.back();
    st.pop_back();
    par[c.u]=c.u;
    par[c.v]=c.v;
    sz[c.u]=c.szu;
    sz[c.v]=c.szv;
}
void upd(ll pos,ll l,ll r,ll u,ll v,ll x,ll y){
    if(u<=l&&r<=v) segtree[pos].push_back({x,y});
    else if(l>v||r<u) return ;
    else{
        ll mid=(l+r)/2;
        upd(2*pos,l,mid,u,v,x,y);
        upd(2*pos+1,mid+1,r,u,v,x,y);
    }
}
void dfs(ll pos,ll l,ll r){
    ll cnt=0;
    for(auto [u,v]:segtree[pos]){
        cnt+=uni(u,v);
    }
    if(l==r){
        ll col=l;
        for(auto i:colors[col]){
            ll p=find_par(i);
            check[p]=1;
        }
        for(auto i:need[col]){
            ll p=find_par(i);
            if(!check[p]) ans=0;
        }
        for(auto i:colors[col]){
            ll p=find_par(i);
            check[p]=0;
        }
    }
    else{
        ll mid=(l+r)>>1;
        dfs(pos<<1,l,mid);
        dfs(pos<<1|1,mid+1,r);
        segtree[pos]={};
    }
    for(int i=1;i<=cnt;i++){
        rollback();
    }
    segtree[pos]={};
}
void solve(){
    ans=1;
    st={};
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        par[i]=i;
        sz[i]=1;
        colors[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        need[b[i]].push_back(i);
    }

    vector<pair<ll,ll>> edges;
    for(int i=1;i<=m;i++){
        ll u,v;
        cin>>u>>v;
        edges.push_back({u,v});
    }
    for(int i=1;i<=n;i++){
        if(a[i]<b[i]){
            ans=0;
        }
    }
    if(ans==0){
        for(int i=1;i<=n;i++) colors[i]={},need[i]={};
        cout<<0<<ntr;
        return ;
    }
    for(auto [u,v]:edges){
        if(max(b[u],b[v])<=min(a[u],a[v])) upd(1,1,n,max(b[u],b[v]),min(a[u],a[v]),u,v);
    }
    dfs(1,1,n);
    for(int i=1;i<=n;i++) colors[i]={},need[i]={};
    cout<<ans<<ntr;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    frep;
    ll t;
    cin>>t;
    while(t--) solve();
}