//
// Created by BigBag on 22.07.2023 12:32:01
//

#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

template<typename T>
ostream& operator << (ostream &os, const vector<T> &v) {
    bool f = 1;
    os << "[";
    for (const auto &x : v) {
        if (!f) {
            os << " ";
        }
        f = 0;
        os << x;
    }
    os << "]";
    return os;
}

const int max_n = 100111, inf = 1000111222;

struct segment_tree {
    int val[max_n], distr[max_n], ans;

    segment_tree() {
        distr[0] = inf;
    }

    void inc(int x) {
        --distr[val[x]];
        ++val[x];
        ++distr[val[x]];
        ans = max(ans, val[x]);
    }

    void dec(int x) {
        --distr[val[x]];
        if (distr[val[x]] == 0 && val[x] == ans) {
            --ans;
        }
        --val[x];
        ++distr[val[x]];
    }

    void op(int x, int val, bool store = true) {
        if (store) {
            ops.push_back({x, val});
        }
        if (val == 1) {
            inc(x);
        } else {
            assert(val == -1);
            dec(x);
        }
    }

    void restore() {
        while (!ops.empty()) {
            op(ops.back().first, -ops.back().second, false);
            ops.pop_back();
        }
    }

    vector<pair<int, int>> ops;
};

segment_tree st;

int DIFF;
int t, n, m, a[max_n];
int sz[max_n], vis[max_n], delta[max_n], val1[max_n], val2[max_n];
vector<int> g3[max_n];
vector<int> all[max_n];
map<pair<int, int>, int> ids;

void dfs3(int v, int p) {
    vis[v] = 1;
    for (int i = 0; i < g3[v].size(); ++i) {
        if (g3[v][i] == p) {
            swap(g3[v][i], g3[v].back());
            g3[v].pop_back();
            break;
        }
    }
    sz[v] = all[v].size();
    for (int to : g3[v]) {
        dfs3(to, v);
        sz[v] += sz[to];
    }
    for (int i = 0; i < g3[v].size(); ++i) {
        if (sz[g3[v].back()] < sz[g3[v][i]]) {
            swap(g3[v].back(), g3[v][i]);
        }
    }
}

int L[max_n], R[max_n];
vector<int> order;

void dfs33(int v) {
    L[v] = order.size();
    for (int x : all[v]) {
        order.push_back(a[x]);
    }
    R[v] = order.size();
    for (int to : g3[v]) {
        dfs33(to);
        if (to != g3[v].back()) {
            R[v] = order.size();
        }
    }
}

void add_rec(int v, int val, bool is_root = true) {
    for (int i = L[v]; i < R[v]; ++i) {
        st.op(order[i], val);
    }
}

void dfs4(int v) {
//    LOG(v, all[v]);
    st.restore();
    for (int to : g3[v]) {
        st.restore();
        dfs4(to);
    }
    if (n > 10) add_rec(v, 1);
    val1[v] = st.ans;
}

void dfs5(int v) {
//    LOG(v, all[v]);
    st.restore();
//    st = st2;
    for (int to : g3[v]) {
        st.restore();
//        st = st2;
        dfs5(to);
    }
    if (n > 10) add_rec(v, -1);
    val2[v] = st.ans;
}

int ADD;

void dfs6(int v) {
//    LOG(v, all[v]);
    for (int to : g3[v]) {
        dfs6(to);
        LOG(v, to, all[to], ADD, val1[to], val2[to]);
        delta[ids[{min(v, to), max(v, to)}]] = ADD + val1[to] + val2[to];
    }
}

int used[max_n], cur_t, tin[max_n], fup[max_n], is_bridge[max_n];
int U[max_n], V[max_n];
vector<int> g[max_n], g2[max_n];

void compress_a() {
    vector<int> v(a, a + n);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    DIFF = v.size() - 1;
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
    }
}

void clr() {
    ids.clear();
    order.clear();
    for (int i = 0; i <= n; ++i) {
        g[i].clear();
        g2[i].clear();
        g3[i].clear();
        used[i] = tin[i] = fup[i] = 0;
        all[i].clear();
    }
    for (int i = 0; i <= m; ++i) {
        is_bridge[i] = 0;
    }
}

void dfs(int v, int pid) {
    tin[v] = fup[v] = ++cur_t;
    used[v] = 1;
    for (int to_id : g[v]) {
        if (to_id == pid) {
            continue;
        }
        const int to = v ^ U[to_id] ^ V[to_id];
        if (!used[to]) {
            dfs(to, to_id);
            if (fup[to] > tin[v]) {
                is_bridge[to_id] = 1;
            }
            fup[v] = min(fup[v], fup[to]);
        } else {
            fup[v] = min(fup[v], tin[to]);
        }
    }
}

void dfs2(int v) {
    used[v] = cur_t;
    all[cur_t].push_back(v);
    for (int to : g2[v]) {
        if (!used[to]) {
            dfs2(to);
        }
    }
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        for (int i = 0; i < m; ++i) {
            cin >> U[i] >> V[i];
            --U[i];
            --V[i];
        }
        compress_a();
        for (int i = 0; i < m; ++i) {
            g[U[i]].push_back(i);
            g[V[i]].push_back(i);
        }
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                dfs(i, -1);
            }
        }
        for (int i = 0; i < m; ++i) {
            if (!is_bridge[i]) {
                g2[U[i]].push_back(V[i]);
                g2[V[i]].push_back(U[i]);
            }
        }
        fill(used, used + n, 0);
        cur_t = 0;
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                ++cur_t;
                dfs2(i);
                LOG(cur_t, all[cur_t]);
            }
        }
        for (int i = 0; i < m; ++i) {
            if (is_bridge[i]) {
                g3[used[U[i]]].push_back(used[V[i]]);
                g3[used[V[i]]].push_back(used[U[i]]);
                ids[{min(used[U[i]], used[V[i]]),
                     max(used[U[i]], used[V[i]])}] = i;
            }
        }
        st.restore();
        int total = 0;
        fill(vis + 1, vis + cur_t + 1, 0);
        for (int i = 1; i <= cur_t; ++i) {
            if (vis[i]) {
                continue;
            }
            dfs3(i, -1);
            order.clear();
            dfs33(i);
            dfs4(i);
            int val = st.ans;
            LOG(i, val);
            total += val;
            ADD = -val;
            auto cops = st.ops;
            st.ops.clear();
            dfs5(i);
            dfs6(i);
            st.restore();
            st.ops = cops;
            st.restore();
        }
        LOG(total);
        for (int i = 0; i < m; ++i) {
            if (is_bridge[i]) {
                cout << total + delta[i];
            } else {
                cout << total;
            }
            if (i + 1 < m) {
                cout << " ";
            }
        }
        cout << "\n";
        clr();
    }
    return 0;
}