#include <bits/stdc++.h>
#define int long long

using namespace std;
using pii = pair<int, int>;

const int maxn = 1e6 + 10;

int T;
int n, root;
int w[maxn];
vector<int> g[maxn];
int dfn[maxn], idx;
vector<int> p;
int f[maxn];

void dfs1(int u, int fa) {
	dfn[u] = ++idx;
	f[u] = fa;
	for (int v : g[u]) {
		if (v == fa) continue;
		dfs1(v, u);
	}
} 

multiset<pii> s, t;

int calc(int u) {
	int x = u;
	while (true) {
		t.insert({w[x], x});
		s.erase(s.find({w[x], x}));
		if (g[x].size() >= 3 || x == root) break;
		x = f[x];
	}
	int res = s.begin()->second;
	while (!t.empty()) {
		pii y = *t.begin();
		s.insert(y);
		t.erase(y);
	}
	return res;
}

signed main() {
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> w[i];
			g[i].clear();
			dfn[i] = f[i] = 0;
		}
		for (int i = 2; i <= n; i++) {
			int u, v;
			cin >> u >> v;
			g[u].push_back(v), g[v].push_back(u);
		}
		for (int i = 1; i <= n; i++) {
			if (g[i].size() > 1) {
				root = i;
				break;
			}
		}
		p.clear();
		for (int i = 1; i <= n; i++) {
			if (g[i].size() == 1) p.push_back(i);
		}
		idx = 0;
		dfs1(root, 0);
		sort(p.begin(), p.end(), [] (int x, int y) {
			return dfn[x] < dfn[y];
		});
		if (p.size() & 1) {
			s.clear();
			for (int i = 1; i <= n; i++) s.insert({w[i], i});
			int u, z, y = 1145141919810ll;
			for (int i = 0; i < p.size(); i++) {
				int x = calc(p[i]);
				if (w[x] < y) {
					y = w[x];
					u = x;
					z = i;
				}
			}
			cout << (p.size() >> 1) + 1 << endl;
			cout << p[z] << " " << u << endl;
			p.erase(p.begin() + z);
			for (int i = 0; i < (p.size() >> 1); i++) cout << p[i] << " " << p[i + (p.size() >> 1)] << endl;
		} else {
			cout << (p.size() >> 1) << endl;
			for (int i = 0; i < (p.size() >> 1); i++) cout << p[i] << " " << p[i + (p.size() >> 1)] << endl;
		}
	}
	return 0;
}