#include <bits/stdc++.h>
using namespace std;
const int inf = 1010000000;
const int mxn = 400010;
int n, a[mxn];
int hd[mxn], nx[mxn], v[mxn], e;
int d[mxn][3];
int o;
void init() {
  e = 0;
  for (int i = 1; i <= n; i++) hd[i] = 0;
}
void ade(int x, int y) {
  nx[++e] = hd[x];
  hd[x] = e;
  v[e] = y;
}
void dfs1(int x, int fa) {
  if (a[x] == 2 || a[x] == o) {
    d[x][0] = 1;
  } else {
    d[x][0] = 2;
  }
  for (int i = hd[x]; i; i = nx[i]) {
    int y = v[i];
    if (y == fa) continue;
    dfs1(y, x);
  }
  int vv, p = 0;
  if (o == a[x]) p = 1;
  for (int i = hd[x]; i; i = nx[i]) {
    int y = v[i];
    if (y == fa) continue;
    if (a[x] == 2 || p == (d[y][0] & 1))
      vv = d[y][0];
    else
      vv = d[y][0] + 1;
    d[x][0] = max(d[x][0], vv);
  }
}
int ls[mxn], rs[mxn], b[mxn], t;
void dfs2(int x, int fa) {
  t = 0;
  for (int i = hd[x]; i; i = nx[i]) {
    int y = v[i];
    if (y == fa) continue;
    b[++t] = y;
  }
  ls[0] = rs[t + 1] = 0;
  int vv, p = 0;
  if (o == a[x]) p = 1;
  for (int i = 1; i <= t; i++) {
    int y = b[i];
    if (a[x] == 2 || p == (d[y][0] & 1))
      vv = d[y][0];
    else
      vv = d[y][0] + 1;
    ls[i] = max(ls[i - 1], vv);
  }
  int v1;
  if (a[x] == 2 || p == (d[x][1] & 1))
    v1 = d[x][1];
  else
    v1 = d[x][1] + 1;
  d[x][2] = inf;
  for (int i = t; i >= 1; i--) {
    int y = b[i];
    if (a[x] == 2 || p == (d[y][0] & 1))
      vv = d[y][0];
    else
      vv = d[y][0] + 1;
    rs[i] = max(rs[i + 1], vv);
    d[y][1] = max(max(rs[i + 1], ls[i - 1]), v1);
    d[x][2] = min(d[x][2], d[y][1]);
  }
  for (int i = hd[x]; i; i = nx[i]) {
    int y = v[i];
    if (y == fa) continue;
    dfs2(y, x);
  }
}
int ans;
void gg() {
  for (int i = 0; i <= n; i++) {
    d[i][0] = d[i][1] = d[i][2] = 0;
  }
  dfs1(1, 0);
  d[1][1] = 1;
  dfs2(1, 0);
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    cnt = max(cnt, min(d[i][0], d[i][2]));
  }
  ans = min(ans, cnt);
}
void sol() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (a[i] == 0)
      a[i] = 2;
    else if (a[i] == 2)
      a[i] = 0;
  }
  init();
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    ade(u, v);
    ade(v, u);
  }
  ans = inf;
  o = 1;
  gg();
  o = 0;
  gg();
  printf("%d\n", ans);
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    sol();
  }
  return 0;
}
