#include <bits/stdc++.h> #include <atcoder/all> using mint = atcoder::static_modint<998244353>; //using mint = atcoder::static_modint<1000000007>; using namespace std; using namespace atcoder; using ld = long double; using ll = long long; #define mp(a,b) make_pair(a,b) #define rep(i,s,n) for(int i=s; i<(int)n; i++) const vector<int> dx{1,0,-1,0},dy{0,1,0,-1}; void test(){ vector<vector<int>> G(200,vector<int>(200)); rep(i,0,100)rep(j,0,100-i){ vector<bool> b(1000); rep(k,1,min(i+1,4))b[G[i-k][j+k]]=true; rep(k,1,min(j+1,4))b[G[i][j-k]]=true; while(b[G[i][j]])G[i][j]++; } rep(i,0,10){ rep(j,0,10)cout << G[i][j] << " "; cout << "\n"; } } void solve(){ int n,k;cin >> n >> k; vector<vector<int>> G(n); rep(i,1,n){ int a,b;cin >> a >> b; a--,b--; G[a].push_back(b); swap(a,b); G[a].push_back(b); } vector<int> a(n); rep(i,0,n)cin >> a[i]; int g=0; queue<int> Q;Q.push(0); vector<int> d(n,-1); d[0]=0; while(Q.size()){ int x=Q.front();Q.pop(); for(auto y:G[x])if(d[y]==-1){ Q.push(y); d[y]=d[x]+1; if(d[y]&1)g^=a[y]; } } if(g)cout << "K\n"; else cout << "P\n"; } int main(){ // test(); ios::sync_with_stdio(false); cin.tie(nullptr); int T;cin >> T; rep(i,0,T)solve(); }