#include <bits/stdc++.h>
//#include <iostream>
//#include <vector>
//#include <algorithm>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foreach(it, v) for(auto it=(v).begin(); it != (v).end(); ++it)

#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define __ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

#define tr(...) cout<<__FUNCTION__<<' '<<__LINE__<<" = ";trace(#__VA_ARGS__, __VA_ARGS__)

using namespace std;

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

template<typename S, typename T> 
ostream& operator<<(ostream& out,pair<S,T> const& p){out<<'('<<p.fi<<", "<<p.se<<')';return out;}

template<typename T>
ostream& operator<<(ostream& out,vector<T> const& v){
int l=v.size();for(int i=0;i<l-1;i++)out<<v[i]<<' ';if(l>0)out<<v[l-1];return out;}

template<typename T>
void trace(const char* name, T&& arg1){cout<<name<<" : "<<arg1<<endl;}

template<typename T, typename... Args>
void trace(const char* names, T&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma-names)<<" : "<<arg1<<" | ";trace(comma+1,args...);}



const int MAXN = 105;
const int INF = (int) 1e9;

int DP[MAXN][MAXN][2][2], dp[MAXN][MAXN][MAXN], subtree[MAXN];

vector<int> g[MAXN];

void compute_inner_dp(int from, vector<int> childs) {
	const int mx_chosen = subtree[from] - 1;

	for (int root_taken = 0; root_taken < 2; root_taken++) {
		for (int i = 0; i <= childs.size(); i++) {
			for (int chosen = 0; chosen <= mx_chosen; chosen++) {
				for (int selected = 0; selected <= childs.size(); selected++) {
					dp[i][chosen][selected] = INF;
				}
			}
		}

		dp[0][0][0] = 0;
		for (int i = 0; i < childs.size(); i++) {
			int to = childs[i];
			for (int chosen = 0; chosen <= mx_chosen; chosen++) {
				for (int selected = 0; selected <= childs.size(); selected++) {
					if (dp[i][chosen][selected] == INF) {
						continue;
					}
					for (int take = 0; take < 2; take++) {
						for (int cur_chosen = take; cur_chosen <= subtree[to] 
							&& chosen + cur_chosen <= mx_chosen && selected + take <= childs.size(); cur_chosen++) {
							int &res = dp[i + 1][chosen + cur_chosen][selected + take];
					
							for (int marked = 0; marked < 2; marked++) {
								if (take && !marked) {
									continue;
								}
								int extra = 0;
								if (root_taken && !marked) {
									extra = 1;
								}
								res = min(res, dp[i][chosen][selected] + DP[to][cur_chosen][take][marked] + extra);
							}
						}
					}
				}
			}
		}

		if (!root_taken) {
			for (int chosen = 0; chosen <= mx_chosen; chosen++) {
				{
					// Selected should be zero only.
					DP[from][chosen][0][0] = dp[childs.size()][chosen][0];
				}
				{
					// TODO: Check
					// if (chosen == 0) {
					// 	continue;
					// }
					int cur_ans = INF;
					for (int selected = 1; selected <= childs.size(); selected++) {
						cur_ans = min(cur_ans, dp[childs.size()][chosen][selected]);
					}
					DP[from][chosen][0][1] = cur_ans + 1;
				}
			}
		} else {
			for (int chosen = 0; chosen <= mx_chosen; chosen++) {
				int cur_ans = INF;
				for (int selected = 0; selected <= childs.size(); selected++) {
					cur_ans = min(cur_ans, dp[childs.size()][chosen][selected]);
				}
				DP[from][chosen + 1][1][1] = cur_ans;
			}
		}
	}
}


void dfs(int from, int par = -1) {
	subtree[from] = 1;
	vector<int> childs;
	for (int to: g[from]) {
		if (to != par) {
			dfs(to, from);
			subtree[from] += subtree[to];
			childs.push_back(to);
		}
	}

	const int mx_chosen = subtree[from];

	for (int chosen = 0; chosen <= mx_chosen; chosen++) {
		for (int take = 0; take < 2; take++) {
			for (int marked = 0; marked < 2; marked++) {
				DP[from][chosen][take][marked] = INF;
			}
		}
	}
	
	// cerr << "here " << subtree[from] << endl;
	compute_inner_dp(from, childs);
}

int main() {
	int T = 1;
	cin >> T;
	int tc = 0;
	int ctr = 0;
	FILE *f = fopen("13.in", "w");
	while (T--) {
		tc++;
		int N, ZEROS = 0, ONES = 0, TWOS = 0;
		cin >> N;
	
		vector<int> color(N);
		for (int i = 0; i < N; i++) {
			int x;
			cin >> x;
			color[i] = x;
			if (x == 0) {
				ZEROS++;
			} else if (x == 1) {
				ONES++;
			} else {
				TWOS++;
			}
		}

		for (int i = 0; i + 1 < N; i++) {
			int from, to;
			cin >> from >> to;
			from--;
			to--;
			g[from].push_back(to);
			g[to].push_back(from);
		}

		// if (tc == 1322) {
		// 	cerr << N << endl;
		// 	for (int i = 0; i < N; i++) {
		// 		cerr << color[i] << " ";
		// 	}
		// 	cerr << endl;
		// 	for (int i = 0; i < N; i++) {
		// 		for (int to: g[i]) {
		// 			if (i < to) {
		// 				cerr << i + 1 << " " << to + 1 << endl;
		// 			}
		// 		}
		// 	}
		// }

		dfs(0, -1);

		// int vert = 0;
		// for (int sz = 0; sz <= N; sz++) {
		// 	tr(sz, DP[vert][sz][1][1]);
		// 	// cout << sz << " " << DP[vert][sz][0][0] << " " << DP[vert][sz][1] << endl;
		// }

		int large = max(ZEROS, N - ZEROS - ONES);
		int small = min(ZEROS, N - ZEROS - ONES);
		// int requiresOnes = min(min(DP[0][large][0][0], DP[0][large][0][1]), DP[0][large][1][1]);
		int requiresOnes = min(DP[0][large][0][1], DP[0][large][1][1]);
		// tr(large);
		// cerr << "requiresOnes " << requiresOnes << endl;

		// tr(ZEROS, ONES, TWOS);

		int ans = 1;
		if (ZEROS && TWOS) {
			ans = 2;
		}
		int ok = false;
		// WA here.
		if (ONES >= requiresOnes) {
			ans = 1;
		}
		if (ZEROS == N || ONES == N || TWOS == N) {
			ans = 0;
		}

		if (ZEROS && ONES && N - ZEROS - ONES > 1 && ans == 2) {
			// fprintf(f, "%d\n", N);
			// for (int i = 0; i < N; i++) {
			// 	fprintf(f, "%d", color[i]);
			// 	if (i + 1 < N) {
			// 		fprintf(f, " ");
			// 	} else {
			// 		fprintf(f, "\n");
			// 	}
			// }
			// for (int i = 0; i < N; i++) {
			// 	for (int to: g[i]) {
			// 		if (i < to) {
			// 			fprintf(f, "%d %d\n", i+1, to+1);
			// 			// cerr << i + 1 << " " << to + 1 << endl;
			// 		}
			// 	}
			// }
			// ctr++;
			// if (ctr == 30) {
			// 	break;
			// }
		}

		// tr(ONES, requiresOnes);
		printf("%d\n", ans);

		for (int i = 0; i < N; i++) {
			g[i].clear();
		}
	}

	cerr << "ctr " << ctr << endl;

    return 0;
}