#include <bits/stdc++.h>
using namespace std;
template <typename T>
void r1(T &x) {
  x = 0;
  char c(getchar());
  int f(1);
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') f = -1;
  for (; '0' <= c && c <= '9'; c = getchar()) x = (x * 10) + (c ^ 48);
  x *= f;
}
template <typename T, typename... Args>
inline void r1(T &t, Args &...args) {
  r1(t);
  r1(args...);
}
const int maxn = 2e5 + 5;
const int maxm = maxn << 1;
const int mod = 1e9 + 7;
typedef int room[maxn];
template <int mod>
struct typemod {
  int z;
  typemod(int a = 0) : z(a) {}
  inline int inc(int a, int b) const {
    return a += b - mod, a + ((a >> 31) & mod);
  }
  inline int dec(int a, int b) const { return a -= b, a + ((a >> 31) & mod); }
  inline int mul(int a, int b) const { return 1ll * a * b % mod; }
  typemod<mod> operator+(const typemod<mod> &x) const {
    return typemod(inc(z, x.z));
  }
  typemod<mod> operator-(const typemod<mod> &x) const {
    return typemod(dec(z, x.z));
  }
  typemod<mod> operator*(const typemod<mod> &x) const {
    return typemod(mul(z, x.z));
  }
  typemod<mod> &operator+=(const typemod<mod> &x) {
    *this = *this + x;
    return *this;
  }
  typemod<mod> &operator-=(const typemod<mod> &x) {
    *this = *this - x;
    return *this;
  }
  typemod<mod> &operator*=(const typemod<mod> &x) {
    *this = *this * x;
    return *this;
  }
  int operator==(const typemod<mod> &x) const { return x.z == z; }
  int operator!=(const typemod<mod> &x) const { return x.z != z; }
};
int n, m;
int fa[maxn], siz[maxn];
int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
void merge(int u, int v) {
  int s1 = getfa(u), s2 = getfa(v);
  if (s1 == s2) return;
  if (siz[s1] > siz[s2])
    fa[s2] = s1, siz[s1] += siz[s2];
  else
    fa[s1] = s2, siz[s2] += siz[s1];
}
struct E {
  int u, v;
} e[maxn];
int head[maxn], cnt;
struct Edge {
  int to, next;
} edg[maxn << 1];
void add(int u, int v) { edg[++cnt] = (Edge){v, head[u]}, head[u] = cnt; }
int deg[maxn], _deg[maxn], vis[maxn];
int Q[maxn], Q1[maxn], a[maxn];
int Solve(int x) {
  int lf(0), i;
  for (i = 1; i <= n; ++i) {
    _deg[i] = deg[i];
    vis[i] = 0;
    if (_deg[i] <= 1) {
      Q[++lf] = i;
      vis[i] = 1;
    }
  }
  int res(0);
  while (lf) {
    static queue<int> q;
    ++res;
    while (!q.empty()) q.pop();
    int lf1(0);
    for (i = 1; i <= lf; ++i) {
      int u = Q[i];
      if (a[u] == x || a[u] == 0) {
        q.push(u);
      } else if (a[u] != x && a[u] != 0) {
        Q1[++lf1] = u;
      }
    }
    lf = lf1;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int i = head[u]; i; i = edg[i].next) {
        int to = edg[i].to;
        if (vis[to]) continue;
        --_deg[to];
        if (_deg[to] <= 1) {
          vis[to] = 1;
          if (a[to] == 0 || a[to] == x)
            q.push(to);
          else
            Q1[++lf] = to;
        }
      }
    }
    for (i = 1; i <= lf; ++i) Q[i] = Q1[i], Q1[i] = 0;
    x = 3 - x;
  }
  return res;
}
void Work() {
  int i, j;
  r1(n);
  cnt = 0;
  for (i = 1; i <= n; ++i) {
    a[i] = 0, head[i] = 0;
    deg[i] = 0;
    fa[i] = i;
    siz[i] = 1;
  }
  for (i = 1; i <= n; ++i) r1(a[i]);
  for (i = 1; i < n; ++i) {
    int u, v;
    r1(u, v);
    if (a[u] == a[v]) merge(u, v);
    e[i] = (E){u, v};
  }
  for (i = 1; i < n; ++i) {
    int u = e[i].u, v = e[i].v;
    int s1 = getfa(u), s2 = getfa(v);
    if (s1 != s2) {
      add(s1, s2);
      add(s2, s1);
      ++deg[s1], ++deg[s2];
    }
  }
  int ans(n);
  ans = min(ans, min(Solve(1), Solve(2)));
  printf("%d\n", ans);
}
signed main() {
  int i, j, t;
  r1(t);
  while (t--) {
    Work();
  }
  return 0;
}
