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

template<typename T>
struct segment_tree {
    T mx[4 * max_n];

    void clr(int v, int l, int r) {
        if (!mx[v] || l == r) {
            if (store_history) {
                ops.push_back({v, mx[v]});
            }
            mx[v] = 0;
            return;
        }
        int mid = (l + r) / 2;
        clr(2 * v, l, mid);
        clr(2 * v + 1, mid + 1, r);
    }

    void build(int v, int l, int r) {
        if (l == r) {
            if (store_history) {
                ops.push_back({v, mx[v]});
            }
            mx[v] = 0;
            return;
        }
        int mid = (l + r) / 2;
        build(2 * v, l, mid);
        build(2 * v + 1, mid + 1, r);
        if (store_history) {
            ops.push_back({v, mx[v]});
        }
        mx[v] = max(mx[2 * v], mx[2 * v + 1]);
    }

    void update(int v, int l, int r, int pos, T value) {
        if (l == r) {
            if (store_history) {
                ops.push_back({v, mx[v]});
            }
            mx[v] += value;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) {
            update(2 * v, l, mid, pos, value);
        } else {
            update(2 * v + 1, mid + 1, r, pos, value);
        }
        if (store_history) {
            ops.push_back({v, mx[v]});
        }
        mx[v] = max(mx[2 * v], mx[2 * v + 1]);
    }

    T get_max(int v, int tl, int tr, int l, int r) {
        if (tl == l && tr == r) {
            return mx[v];
        }
        int mid = (tl + tr) / 2;
        if (r <= mid) {
            return get_max(2 * v, tl, mid, l, r);
        } else if (l > mid) {
            return get_max(2 * v + 1, mid + 1, tr, l, r);
        }
        return max(get_max(2 * v, tl, mid, l, mid), get_max(2 * v + 1, mid + 1, tr, mid + 1, r));
    }

    void stop_store_history() {
        store_history = false;
        ops.clear();
    }

    void start_store_history() {
        store_history = true;
        ops.clear();
    }

    void restore() {
        while (!ops.empty()) {
            mx[ops.back().first] = ops.back().second;
            ops.pop_back();
        }
    }

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

segment_tree<int> st;

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]);
        }
    }
}

void add(int v, int val) {
    for (int x : all[v]) {
        st.update(1, 0, n - 1, a[x], val);
    }
}

void add_rec(int v, int val) {
    add(v, val);
    for (int to : g3[v]) {
        add_rec(to, val);
    }
}

void dfs4(int v) {
//    LOG(v, all[v]);
    st.clr(1, 0, n - 1);
    for (int to : g3[v]) {
        st.clr(1, 0, n - 1);
        dfs4(to);
    }
    add(v, 1);
    for (int i = 0; i + 1 < g3[v].size(); ++i) {
        add_rec(g3[v][i], 1);
    }
    val1[v] = st.get_max(1, 0, n - 1, 0, n - 1);
}

void dfs5(int v) {
//    LOG(v, all[v]);
    st.restore();
//    st = st2;
    for (int to : g3[v]) {
        st.restore();
//        st = st2;
        dfs5(to);
    }
    for (int i = 0; i + 1 < g3[v].size(); ++i) {
        add_rec(g3[v][i], -1);
    }
    add(v, -1);
    val2[v] = st.get_max(1, 0, n - 1, 0, n - 1);
}

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());
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
    }
}

void clr() {
    ids.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);
        }
    }
}

const bool debug = 0;

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

    if (debug) {
        t = 10;
    } else {
        cin >> t;
    }
    while (t--) {
        if (debug) {
            n = m = 100000;
            --m;
            for (int i = 0; i < n; ++i) {
                a[i] = i % 100;
            }
            for (int i = 0; i < m; ++i) {
                U[i] = i;
                V[i] = i + 1;
            }
        } else {
            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.build(1, 0, n - 1);
        int total = 0;
        fill(vis + 1, vis + cur_t + 1, 0);
        for (int i = 1; i <= cur_t; ++i) {
            if (vis[i]) {
                continue;
            }
            st.stop_store_history();
            dfs3(i, -1);
            dfs4(i);
            int val = st.get_max(1, 0, n - 1, 0, n - 1);
            LOG(i, val);
            total += val;
            ADD = -val;
            st.start_store_history();
            dfs5(i);
            dfs6(i);
        }
        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;
}