#include<bits/stdc++.h>
// #include <sys/resource.h>
#define ll long long
// #define ll int
#define f(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
// ll binpow(ll a, ll b, ll md){ll res=1;a%=mod;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
using namespace std;
const int N=512;
int n,timer=0;
vector<vector<int> > v;
vector<int> st,en,a,freq,tot,cnt;
vector<bool> vis;
void dfs(int cur, int parent)
{
st[cur]=timer++;
a.pb(cur);
f(i,0,sz(v[cur]))
{
int node=v[cur][i];
if(node!=parent)
dfs(node,cur);
}
en[cur]=timer-1;
}
struct Query {
int l, r, idx;
bool operator<(Query other) const
{
return make_pair(l / N, r) <
make_pair(other.l / N, other.r);
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #ifndef ONLINE_JUDGE
// freopen("chainblock_input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
int z=1;
cin>>z;
int mx=0;
f(i,1,z+1)
{
timer=0;
cout<<"Case #"<<i<<": ";
cin>>n;
v.clear(),st.clear(),en.clear(),freq.clear(),cnt.clear();
v.rz(n+2),st.rz(n+2),en.rz(n+2),freq.rz(n+2),cnt.rz(n+2);
f(j,0,n-1)
{
int l,r;
cin>>l>>r;
v[l].pb(r),v[r].pb(l);
}
f(i,1,n+1)
{
cin>>freq[i];
cnt[freq[i]]++;
}
dfs(1,1);
tot.clear();
tot.rz(n+1);
vector<Query> queries;
f(i,2,n+1)
queries.pb({st[i],en[i],i-2});
sort(all(queries));
int cur_l = 0;
int cur_r = -1,ans=0,cur=0;
for (Query q : queries) {
while (cur_l > q.l) {
cur_l--;
// add(cur_l);
int fr=freq[a[cur_l]];
if(tot[fr]==0)
cur++;
tot[fr]++;
if(tot[fr]==cnt[fr])
cur--;
}
while (cur_r < q.r) {
cur_r++;
//add(cur_r);
int fr=freq[a[cur_r]];
if(tot[fr]==0)
cur++;
tot[fr]++;
if(tot[fr]==cnt[fr])
cur--;
}
while (cur_l < q.l) {
//remove(cur_l);
int fr=freq[a[cur_l]];
if(tot[fr]==1)
cur--;
if(tot[fr]==cnt[fr])
cur++;
tot[fr]--;
cur_l++;
}
while (cur_r > q.r) {
//remove(cur_r);
int fr=freq[a[cur_r]];
if(tot[fr]==1)
cur--;
if(tot[fr]==cnt[fr])
cur++;
tot[fr]--;
cur_r--;
}
if(cur==0)
ans++;
}
cout<<ans<<"\n";
a.clear();
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KLy8gI2luY2x1ZGUgPHN5cy9yZXNvdXJjZS5oPgoKI2RlZmluZSBsbCBsb25nIGxvbmcKLy8gI2RlZmluZSBsbCBpbnQKI2RlZmluZSBmKGksYSxiKSBmb3IoaW50IGk9YTtpPGI7aSsrKQojZGVmaW5lIG1vZCAxMDAwMDAwMDA3Ci8vICNkZWZpbmUgbW9kIDk5ODI0NDM1MyAKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSB1bmlxKHYpICh2KS5lcmFzZSh1bmlxdWUoYWxsKHYpKSwodikuZW5kKCkpCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSByZihpLGEsYikgZm9yKGludCBpPWE7aT49YjtpLS0pCiNkZWZpbmUgc2MoYSkgc2NhbmYoIiVsbGQiLCZhKQojZGVmaW5lIHBmIHByaW50ZgojZGVmaW5lIHN6KGEpIChpbnQpKGEuc2l6ZSgpKQojZGVmaW5lIHBzZiBwdXNoX2Zyb250CiNkZWZpbmUgcHBmIHBvcF9mcm9udAojZGVmaW5lIHBwYiBwb3BfYmFjawojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIHBxIHByaW9yaXR5X3F1ZXVlCiNkZWZpbmUgYWxsKHMpIHMuYmVnaW4oKSxzLmVuZCgpCiNkZWZpbmUgc3AoYSkgc2V0cHJlY2lzaW9uKGEpCiNkZWZpbmUgcnogcmVzaXplCiNkZWZpbmUgbGQgbG9uZyBkb3VibGUKI2RlZmluZSBpbmYgKGxsKTFlMTgKI2RlZmluZSB1YiB1cHBlcl9ib3VuZAojZGVmaW5lIGxiIGxvd2VyX2JvdW5kCiNkZWZpbmUgYnMgYmluYXJ5X3NlYXJjaAojZGVmaW5lIGViIGVtcGxhY2VfYmFjawpjb25zdCBkb3VibGUgcGkgPSBhY29zKC0xKTsKbGwgYmlucG93KGxsIGEsIGxsIGIpe2xsIHJlcz0xO3doaWxlKGIhPTApe2lmKGImMSlyZXMqPWE7YSo9YTtiPj49MTt9cmV0dXJuIHJlczt9Ci8vIGxsIGJpbnBvdyhsbCBhLCBsbCBiLCBsbCBtZCl7bGwgcmVzPTE7YSU9bW9kO3doaWxlKGIhPTApe2lmKGImMSlyZXMqPWEscmVzJT1tZDthKj1hLGElPW1kO2I+Pj0xO31yZXR1cm4gcmVzJW1kO30KIAp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE49NTEyOwppbnQgbix0aW1lcj0wOwp2ZWN0b3I8dmVjdG9yPGludD4gPiB2Owp2ZWN0b3I8aW50PiBzdCxlbixhLGZyZXEsdG90LGNudDsKdmVjdG9yPGJvb2w+IHZpczsKIAp2b2lkIGRmcyhpbnQgY3VyLCBpbnQgcGFyZW50KQp7CiAgICBzdFtjdXJdPXRpbWVyKys7CiAgICBhLnBiKGN1cik7CiAgICBmKGksMCxzeih2W2N1cl0pKQogICAgewogICAgICAgIGludCBub2RlPXZbY3VyXVtpXTsKICAgICAgICBpZihub2RlIT1wYXJlbnQpCiAgICAgICAgICAgIGRmcyhub2RlLGN1cik7CiAgICB9CiAgICBlbltjdXJdPXRpbWVyLTE7Cn0KCnN0cnVjdCBRdWVyeSB7CiAgICBpbnQgbCwgciwgaWR4OwogICAgYm9vbCBvcGVyYXRvcjwoUXVlcnkgb3RoZXIpIGNvbnN0CiAgICB7CiAgICAgICAgcmV0dXJuIG1ha2VfcGFpcihsIC8gTiwgcikgPAogICAgICAgICAgICAgICBtYWtlX3BhaXIob3RoZXIubCAvIE4sIG90aGVyLnIpOwogICAgfQp9OwoKaW50IG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICAvLyBmcmVvcGVuKCJpbnB1dC50eHQiLCJyIixzdGRpbik7CiAgICAvLyBmcmVvcGVuKCJvdXRwdXQudHh0IiwidyIsc3Rkb3V0KTsKLy8gI2lmbmRlZiBPTkxJTkVfSlVER0UKICAgIC8vIGZyZW9wZW4oImNoYWluYmxvY2tfaW5wdXQudHh0IiwiciIsc3RkaW4pOwogICAgLy8gZnJlb3Blbigib3V0cHV0LnR4dCIsInciLHN0ZG91dCk7Ci8vICNlbmRpZgogICAgaW50IHo9MTsKICAgIGNpbj4+ejsKICAgIGludCBteD0wOwogICAgZihpLDEseisxKQogICAgewogICAgICAgIHRpbWVyPTA7CiAgICAgICAgY291dDw8IkNhc2UgIyI8PGk8PCI6ICI7CiAgICAgICAgY2luPj5uOwogICAgICAgIHYuY2xlYXIoKSxzdC5jbGVhcigpLGVuLmNsZWFyKCksZnJlcS5jbGVhcigpLGNudC5jbGVhcigpOwogICAgICAgIHYucnoobisyKSxzdC5yeihuKzIpLGVuLnJ6KG4rMiksZnJlcS5yeihuKzIpLGNudC5yeihuKzIpOwogICAgICAgIGYoaiwwLG4tMSkKICAgICAgICB7CiAgICAgICAgICAgIGludCBsLHI7CiAgICAgICAgICAgIGNpbj4+bD4+cjsKICAgICAgICAgICAgdltsXS5wYihyKSx2W3JdLnBiKGwpOwogICAgICAgIH0KICAgICAgICBmKGksMSxuKzEpCiAgICAgICAgewogICAgICAgICAgICBjaW4+PmZyZXFbaV07CiAgICAgICAgICAgIGNudFtmcmVxW2ldXSsrOwogICAgICAgIH0KICAgICAgICBkZnMoMSwxKTsKICAgICAgICB0b3QuY2xlYXIoKTsKICAgICAgICB0b3QucnoobisxKTsKICAgICAgICB2ZWN0b3I8UXVlcnk+IHF1ZXJpZXM7CiAgICAgICAgZihpLDIsbisxKQogICAgICAgICAgICBxdWVyaWVzLnBiKHtzdFtpXSxlbltpXSxpLTJ9KTsKICAgICAgICBzb3J0KGFsbChxdWVyaWVzKSk7CiAgICAgICAgaW50IGN1cl9sID0gMDsKICAgICAgICBpbnQgY3VyX3IgPSAtMSxhbnM9MCxjdXI9MDsKICAgICAgICBmb3IgKFF1ZXJ5IHEgOiBxdWVyaWVzKSB7CiAgICAgICAgICAgIHdoaWxlIChjdXJfbCA+IHEubCkgewogICAgICAgICAgICAgICAgY3VyX2wtLTsKICAgICAgICAgICAgICAgIC8vIGFkZChjdXJfbCk7CiAgICAgICAgICAgICAgICBpbnQgZnI9ZnJlcVthW2N1cl9sXV07CiAgICAgICAgICAgICAgICBpZih0b3RbZnJdPT0wKQogICAgICAgICAgICAgICAgICAgIGN1cisrOwogICAgICAgICAgICAgICAgdG90W2ZyXSsrOwogICAgICAgICAgICAgICAgaWYodG90W2ZyXT09Y250W2ZyXSkKICAgICAgICAgICAgICAgICAgICBjdXItLTsKICAgICAgICAgICAgfQogICAgICAgICAgICB3aGlsZSAoY3VyX3IgPCBxLnIpIHsKICAgICAgICAgICAgICAgIGN1cl9yKys7CiAgICAgICAgICAgICAgICAvL2FkZChjdXJfcik7CiAgICAgICAgICAgICAgICBpbnQgZnI9ZnJlcVthW2N1cl9yXV07CiAgICAgICAgICAgICAgICBpZih0b3RbZnJdPT0wKQogICAgICAgICAgICAgICAgICAgIGN1cisrOwogICAgICAgICAgICAgICAgdG90W2ZyXSsrOwogICAgICAgICAgICAgICAgaWYodG90W2ZyXT09Y250W2ZyXSkKICAgICAgICAgICAgICAgICAgICBjdXItLTsKICAgICAgICAgICAgfQogICAgICAgICAgICB3aGlsZSAoY3VyX2wgPCBxLmwpIHsKICAgICAgICAgICAgICAgIC8vcmVtb3ZlKGN1cl9sKTsKICAgICAgICAgICAgICAgIGludCBmcj1mcmVxW2FbY3VyX2xdXTsKICAgICAgICAgICAgICAgIGlmKHRvdFtmcl09PTEpCiAgICAgICAgICAgICAgICAgICAgY3VyLS07CiAgICAgICAgICAgICAgICBpZih0b3RbZnJdPT1jbnRbZnJdKQogICAgICAgICAgICAgICAgICAgIGN1cisrOwogICAgICAgICAgICAgICAgdG90W2ZyXS0tOwogICAgICAgICAgICAgICAgY3VyX2wrKzsKICAgICAgICAgICAgfQogICAgICAgICAgICB3aGlsZSAoY3VyX3IgPiBxLnIpIHsKICAgICAgICAgICAgICAgIC8vcmVtb3ZlKGN1cl9yKTsKICAgICAgICAgICAgICAgIGludCBmcj1mcmVxW2FbY3VyX3JdXTsKICAgICAgICAgICAgICAgIGlmKHRvdFtmcl09PTEpCiAgICAgICAgICAgICAgICAgICAgY3VyLS07CiAgICAgICAgICAgICAgICBpZih0b3RbZnJdPT1jbnRbZnJdKQogICAgICAgICAgICAgICAgICAgIGN1cisrOwogICAgICAgICAgICAgICAgdG90W2ZyXS0tOwogICAgICAgICAgICAgICAgY3VyX3ItLTsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZihjdXI9PTApCiAgICAgICAgICAgICAgICBhbnMrKzsKICAgICAgICB9CiAgICAgICAgY291dDw8YW5zPDwiXG4iOwogICAgICAgIGEuY2xlYXIoKTsKICAgIH0KfSA=