#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

//#ifndef DLOCAL
//   #define cin fin
//   #define cout fout
//   ifstream cin(".in");
//   ofstream cout(".out");
//#endif

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 2e5 + 5;

namespace DSU {
   int dsu[nmax];
   int cc;
   void init(int n) {
      cc = n;
      for(int i = 1; i <= n; i++) dsu[i] = i;
   }
   int f(int x) { return dsu[x] == x? x : dsu[x] = f(dsu[x]); }
   void unite(int x, int y) {
      x = f(x);
      y = f(y);
      if(x == y) return;
      dsu[x] = y;
      cc--;
   }
}

vector<int> g[nmax];
int col[nmax];
vector<tii> bycol[nmax];
vector<int> atrnodes[nmax];
int couldbe[nmax];

int pri[nmax];
multiset<int> asked[nmax];
int timesreq[nmax], atrfreq[nmax];
int d[nmax];



int initpri(int node, int f) {
   if(col[node] != col[f]) return 0;
   int once = 0, twice = 0;
   for(auto x : g[node]) {
      if(x == f) continue;
      int a = initpri(x, node);
      //cerr << node << " -> " << x << '\t' << a << '\n';
      twice |= once & a;
      once |= a;
   }
   int c = 0;
   while(twice) twice >>= 1, once >>= 1, c++;
   while(once & 1) once >>= 1, c++;
   pri[node] = c;
   
   return (once | 1) << c;
}


template<typename CB> void initd(CB&& cb, int node, int f) {
   if(!cb(node)) return;
   for(auto x : g[node]) {
      if(x == f || !cb(x)) continue;
      d[x] = d[node] + 1;
      initd(cb, x, node);
      
   }
}

template<typename CB> void modS(CB&& cb, int node, int f, int mx) {
   if(col[node] != col[f]) return;
   if(pri[node] >= mx) return;
   
   cb(node);
   
   for(auto x : g[node]) {
      if(x == f) continue;
      modS(cb, x, node, mx);
   }
   return;
}

multiset<int> dfs(int ccol, int root, int f) {
   int tranz = 0;
   for(auto [ncol, anchor, troot] : bycol[ccol]) {
      if(ncol == f) continue;
      
      auto S = dfs(ncol, troot, ccol);
      if(sz(asked[anchor]) < sz(S)) swap(asked[anchor], S);
      for(auto x : S) asked[anchor].emplace(x);
      tranz++;
   }
   
   initpri(root, root);
   //for(auto x : atrnodes[ccol])
      //cerr << pri[x] << ' ';
   //cerr << '\n';
   //for(auto x : atrnodes[ccol]) {
      //cerr << x << ": ";
      //for(auto a : asked[x]) cerr << a << ' ';
      //cerr << '\n';
   //}
   //cerr << '\n';
   
   for(auto centr : atrnodes[ccol]) {
      d[centr] = 0;
      initd([&](int node) {
         return col[node] == col[root] && pri[node] <= pri[centr]; 
      }, centr, centr);
      
      for(auto cd : asked[centr]) {
         if(cd == 0) atrfreq[centr]++;
         else timesreq[cd]++;
      }
      
      #warning fa prefixe sufixe daca merge macar asta
      
      for(auto y : g[centr]) {
         modS([&](int node) {
            for(auto cd : asked[node]) {
               if(cd == d[node]) atrfreq[centr]++;
               if(cd > d[node]) timesreq[cd - d[node]]++;
            }
         }, y, centr, pri[centr]);
      }
      
      for(auto y : g[centr]) {
         modS([&](int node) {
            for(auto cd : asked[node]) {
               if(cd > d[node])
                  timesreq[cd - d[node]]--;
            }
         }, y, centr, pri[centr]);
         
         
         modS([&](int node) {
            atrfreq[node] += timesreq[d[node]];
         }, y, centr, pri[centr]);
         
         modS([&](int node) {
            for(auto cd : asked[node]) {
               if(cd > d[node])
                  timesreq[cd - d[node]]++;
            }
         }, y, centr, pri[centr]);
      }
      
      
      for(auto y : g[centr]) {
         modS([&](int node) {
            for(auto cd : asked[node]) {
               if(cd > d[node]) timesreq[cd - d[node]]--;
            }
         }, y, centr, pri[centr]);
      }
      for(auto cd : asked[centr]) {
         if(cd == 0);
         else timesreq[cd]--;
      }
      
      //cerr << centr;
      //cerr << "\t\t\t";
      //for(auto x : atrnodes[ccol]) cerr << atrfreq[x] << ' ';
      //cerr << '\n';
      
   }

   d[root] = 0;
   initd([&](int node) {
      return col[node] == col[root];
   }, root, root);
   
   multiset<int> S;
   for(auto x : atrnodes[ccol]) {
      //cerr << x << ' ' << atrfreq[x] << ' '<< tranz << '\n';
      if(atrfreq[x] == tranz && S.count(d[x]) == 0) S.emplace(d[x]), couldbe[x] = 1;
   }
   
   //cerr << col[root] << ": ";
   //for(auto x : S) cerr << x << ' ';
   //cerr << '\n';
   
   return S;
}

int atrcounty[nmax];

void reconstr(int ccol, int root, int f, int target) {
   d[root] = 0;
   initd([&](int node) {
      return col[node] == col[root];
   }, root, root);
   
   int desire = -1;
   for(auto x : atrnodes[ccol]) {
      if(d[x] == target && couldbe[x]) { desire = x; break; }
   }
   //cerr << desire << '\n';
   
   atrcounty[ccol] = desire;
   
   d[desire] = 0;
   initd([&](int node) {
      return col[node] == col[root];
   }, desire, desire);
   
   for(auto [ncol, anchor, troot] : bycol[ccol]) {
      if(ncol == f) continue;
      
      reconstr(ncol, troot, ccol, d[anchor]);
   }
   return;
}


signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n, k;
   cin >> n >> k;
   for(int i = 1; i <= n; i++) {
      cin >> col[i];
      atrnodes[col[i]].emplace_back(i);
   }
   
   DSU::init(n);
   for(int j = 0, x, y; j < n - 1; j++) {
      cin >> x >> y;
      if(col[x] == col[y]) DSU::unite(x, y);
      else {
         bycol[col[x]].emplace_back(col[y], x, y);
         bycol[col[y]].emplace_back(col[x], y, x);
      }
      
      g[x].emplace_back(y);
      g[y].emplace_back(x);
   } 
   if(DSU::cc != k)  { cout << "NE\n"; return 0; }
   
   auto S = dfs(1, atrnodes[1].back(), 1);
   if(sz(S) == 0) { cout << "NE\n"; return 0; }
   cout << "DA\n";
   
   reconstr(1, atrnodes[1].back(), 1, *S.begin());
   
   for(int i = 1; i <= k; i++)
      cout << atrcounty[i] << ' ';
   cout << '\n';
   
   
      
      
   
   
}

/**
      Binecuvanteaza Doamne Ukraina.
--
*/