//
// 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;
}

template<typename Edge>
class GraphIterator {
public:
    class OutgoingEdges {
    public:
        OutgoingEdges(const GraphIterator *g, int l, int r): g(g), l(l), r(r) {
        }

        const Edge* begin() const {
            if (l == r) {
                return 0;
            }
            return &g->prepared_edges[l];
        }

        const Edge* end() const {
            if (l == r) {
                return 0;
            }
            return &g->prepared_edges[r];
        }

        int size() const {
            return r - l;
        }

    private:
        int l, r;
        const GraphIterator *g;
    };

    void clear() {
        prepared_edges.clear();
        edges.clear();
        start.clear();
        prepared = false;
    }

    void add_edge(int from, const Edge &e) {
        assert(!prepared && from >= 0);
        edges.push_back({from, e});
    }

    void prepare() {
        assert(!prepared);
        int n = 0;
        for (const auto &e : edges) {
            n = max(n, e.first);
        }
        n += 2;
        start.resize(n);
        for (const auto &e : edges) {
            ++start[e.first + 1];
        }
        for (int i = 1; i < n; ++i) {
            start[i] += start[i - 1];
        }
        prepared_edges.resize(edges.size() + 1);
        auto counter = start;
        for (const auto &e : edges) {
            prepared_edges[counter[e.first]++] = e.second;
        }
        prepared = true;
    }

    OutgoingEdges operator [] (int from) const {
        assert(prepared);
        if (from < 0 || from + 1 >= start.size()) {
            return {this, 0, 0};
        }
        return {this, start[from], start[from + 1]};
    }

private:
    vector<Edge> prepared_edges;
    vector<pair<int, Edge>> edges;
    vector<int> start;
    bool prepared = false;
};

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], parent[max_n];
int sz[max_n], vis[max_n], delta[max_n], val1[max_n], val2[max_n];
vector<int> g3[max_n];
GraphIterator<int> all;

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]) {
        parent[to] = 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);
    }
    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);
    }
    add_rec(v, -1);
    val2[v] = st.ans;
}

int ADD;

void dfs6(int v) {
    for (int to : g3[v]) {
        dfs6(to);
        delta[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];
GraphIterator<int> g, g2;

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() {
    order.clear();
    g.clear();
    g2.clear();
    all.clear();
    for (int i = 0; i <= n; ++i) {
        used[i] = tin[i] = fup[i] = 0;
        parent[i] = -1;
        g3[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.add_edge(cur_t, 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.add_edge(U[i], i);
            g.add_edge(V[i], i);
        }
        g.prepare();
        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.add_edge(U[i], V[i]);
                g2.add_edge(V[i], U[i]);
            }
        }
        g2.prepare();
        fill(used, used + n, 0);
        cur_t = 0;
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                ++cur_t;
                dfs2(i);
            }
        }
        all.prepare();
        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]]);
            }
        }
        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]) {
                int to = used[U[i]];
                if (parent[used[V[i]]] == used[U[i]]) {
                    to = used[V[i]];
                }
                assert(parent[to] == (used[U[i]] ^ used[V[i]] ^ to));
                cout << total + delta[to];
            } else {
                cout << total;
            }
            if (i + 1 < m) {
                cout << " ";
            }
        }
        cout << "\n";
        clr();
    }
    return 0;
}