#include <bits/stdc++.h>
using namespace std;
#define el "\n"
#define FOR(i,a,b) for(int i = (a), _b = (b); i <= _b; i++)
#define FORD(i,a,b) for(int i = (a), _b = (b); i >= _b; i--)
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define lg(x) __lg(x)
#define alla(a,n) a+1,a+n+1
#define ll long long
#define debug(x) cout << (x) << " ";
#define c_bit(msk) __builtin_popcount(msk)
template <class T> bool maxi(T &x, T y) { if(x < y) { x = y ; return true ;} return false;}
template <class T> bool mini(T &x, T y) { if(x > y) { x = y ; return true ;} return false;}
const int N = 2e5 + 2;
int n, a[N], k;
vector<int> adj[N];
pair<int, int> E[N];
void inp()
{
cin >> n >> k;
FOR(i, 1, n - 1) {
int x, y; cin >> x >> y;
E[i] = {x, y};
}
FOR(i, 1, n) cin >> a[i];
}
/* Try your best
No regrets */
namespace subtask_1
{
struct DSU
{
int lab[N];
int root(int x)
{
return lab[x] < 0 ? x : lab[x] = root(lab[x]);
}
bool joint(int x, int y)
{
x = root(x); y = root(y);
if(x == y) return 0;
if(lab[x] > lab[y]) swap(x, y);
lab[x] += lab[y];
lab[y] = x;
return 1;
}
} dsu;
bool ok[N];
int temp[N];
int cnt[N];
void slv()
{
int ans = k - 1;
for(int msk = 0; msk < (1 << k); msk++) {
FOR(i, 1, n) temp[i] = a[i];
for(int i = 1; i <= k; i++) ok[i] = 0;
int uwu = 0;
for(int color = 0; color < k; color++) if(msk >> color & 1) {
if(!uwu) uwu = color + 1;
ok[color + 1] = 1;
}
FOR(i, 1, n) if(ok[temp[i]]) temp[i] = uwu;
for(int i = 1; i <= n; i++) dsu.lab[i] = -1;
FOR(i, 1, n - 1) {
int x = E[i].first, y = E[i].second;
if(temp[x] == temp[y] && temp[x] == uwu) {
dsu.joint(x, y);
}
}
for(int i = 1; i <= k; i++) cnt[i] = 0;
for(int i = 1; i <= n; i++) cnt[temp[i]]++;
// for(int i = 1; i <= n; i++) cout << temp[i] << " "; cout << el;
bool oke = 0;
for(int i = 1; i <= n; i++) {
int p = dsu.root(i);
int number = dsu.lab[p];
if(-number == cnt[temp[i]]) {
oke = 1;
break;
}
}
if(oke) {
if(!msk) ans = 0;
else mini(ans, c_bit(msk) - 1);
}
}
cout << ans;
}
}
/* Code slowly, think carefully */
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define __Azul__ "capital_city"
if(fopen(__Azul__".inp", "r")) {
freopen(__Azul__".inp", "r", stdin);
freopen(__Azul__".out", "w", stdout);
}
bool qs = 0;
int T = 1;
if(qs) cin >> T;
while(T--) {
inp();
subtask_1::slv();
}
cerr << "\nTime" << 0.001 * clock() << "s "; return 0;
}
