1810E - Monsters - CodeForces Solution

//#pragma gcc target("avx2")
//#pragma gcc("Ofast")
#include <bits/stdc++.h>
#define int long long int 
#define F first
#define S second
#define pii pair<int,int>
using namespace std;

inline int ceil(int a, int b) {
    return a <= 0 ? 0LL : (a + b - 1) / b;
}

struct DSU {
    vector<int> dsu, sz;
    vector< priority_queue<pii, vector<pii>, greater<pii>> > edges; //should be a min heap
    DSU() {}
    DSU(int N) {
        dsu = vector<int>(N);
        sz = vector<int>(N, 1);
        edges = vector<priority_queue<pii, vector<pii>, greater<pii>> >(N);
        iota(dsu.begin(), dsu.end(), 0);
    }

    int Flat(int x) {
        if(x == dsu[x]) return x;
        dsu[x] = Flat(dsu[x]);
        sz[x] = sz[dsu[x]];
        return dsu[x];
    }

    bool Merge(int a, int b) {
        a = Flat(a);
        b = Flat(b);
        //merge sets 
        if(sz[a] > sz[b]) swap(a, b);
        if(a == b) return false;
        sz[b] += sz[a];
        while(edges[a].size()) {
            auto [w, v] = edges[a].top(); edges[a].pop(); //O(log^2)
            if(Flat(v) != b) {
                edges[b].push({w, v}); 
            }
        }
        dsu[a] = b;
        return true;
    }
} dsu;

void solve() {
    int N, M, u, v;
    cin >> N >> M;
    vector<int> a = vector<int>(N);
    vector<bool> vis = vector<bool>(N, 0);
    vector<vector<int>> adj = vector<vector<int>>(N, vector<int>());
    for(int i = 0; i < N; i++) cin >> a[i];
    for(int i = 0; i < M; i++) {
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dsu = DSU(N);
    for(int i = 0; i < N; i++) if(a[i] == 0 && vis[i] == 0) {
        //cout << "starting at " << i << endl; 
        for(int u : adj[i]) {
            dsu.edges[i].push({a[u], u});
        }
        vis[i] = 1;
        int t = dsu.Flat(i);
        while(dsu.edges[t].size()){
            auto [w, v] = dsu.edges[t].top();
            //cout << "w = " << w << ", v = " << v << endl;
            if(w > dsu.sz[t]) break; //can't add the edge any more
            
            dsu.edges[t].pop();
            //connects to a different connected component
            if(!vis[v]) {
                vis[v] = 1;
                for(auto x : adj[v]) dsu.edges[v].push({a[x], x});
            }
            if(dsu.Merge(t, v)) {
                //cout << "merged " << i << " and " << v << endl;
                //cout << "size: " << dsu.sz[dsu.Flat(i)] << ", no. edges: " << dsu.edges[dsu.Flat(i)].size() << endl;
            }
            t = dsu.Flat(i);
        }
    }
    int t = dsu.Flat(1);
    cout << (dsu.sz[t] == N ? "YES" : "NO") << endl;
    //hi 
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        solve();
    }
}