#include <bits/stdc++.h>
using namespace std;
const int maxN = 201000;
vector<int> g[maxN];
int color[maxN];
void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    g[i].clear();
    cin >> color[i];
  }
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int res = 500000;
  {
    set<int> leaves[3];
    vector<int> used(n, 0);
    vector<int> deg(n, 0);
    for (int i = 0; i < n; ++i) {
      deg[i] = g[i].size();
      if (g[i].size() <= 1) {
        leaves[color[i]].insert(i);
      }
    }
    int cres = 0;
    int removed = 0;
    int st = 1;
    while (removed < n) {
      queue<int> q;
      for (auto v : leaves[0]) {
        q.push(v);
      }
      leaves[0].clear();
      for (auto v : leaves[st]) {
        q.push(v);
      }
      leaves[st].clear();
      while (!q.empty()) {
        int cur = q.front();
        q.pop();
        ++removed;
        used[cur] = 1;
        for (int i = 0; i < g[cur].size(); ++i) {
          int to = g[cur][i];
          --deg[to];
          if (!used[to] && (color[to] == 0 || color[to] == st) &&
              deg[to] <= 1) {
            q.push(to);
          } else if (!used[to] && color[to] == 3 - st && deg[to] <= 1) {
            leaves[color[to]].insert(to);
          }
        }
      }
      st = 3 - st;
      ++cres;
    }
    res = min(res, cres);
  }
  {
    set<int> leaves[3];
    vector<int> used(n, 0);
    vector<int> deg(n, 0);
    for (int i = 0; i < n; ++i) {
      deg[i] = g[i].size();
      if (g[i].size() <= 1) {
        leaves[color[i]].insert(i);
      }
    }
    int cres = 0;
    int removed = 0;
    int st = 2;
    while (removed < n) {
      queue<int> q;
      for (auto v : leaves[0]) {
        q.push(v);
      }
      leaves[0].clear();
      for (auto v : leaves[st]) {
        q.push(v);
      }
      leaves[st].clear();
      while (!q.empty()) {
        int cur = q.front();
        q.pop();
        ++removed;
        used[cur] = 1;
        for (int i = 0; i < g[cur].size(); ++i) {
          int to = g[cur][i];
          --deg[to];
          if (!used[to] && (color[to] == 0 || color[to] == st) &&
              deg[to] <= 1) {
            q.push(to);
          } else if (!used[to] && color[to] == 3 - st && deg[to] <= 1) {
            leaves[color[to]].insert(to);
          }
        }
      }
      st = 3 - st;
      ++cres;
    }
    res = min(res, cres);
  }
  cout << res << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  int t;
  cin >> t;
  for (int tt = 0; tt < t; ++tt) {
    solve();
  }
  return 0;
}
