#ifdef LOCAL
#else
#include "stations.h"
#endif
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
#ifdef LOCAL
#else
#endif
int find_next_station(int s, int t, vector<int> c) {
bool ok = true;
sort(c.begin(), c.end());
int sz = c.size();
if (sz == 1) {
return c[0];
}
for (int i = 0; i < sz; i++) {
if (t == c[i]) {
return c[i];
}
}
if (s == 0) {
for (int i = 0; i < sz; i++) {
if (t < c[i]) {
return c[i];
}
}
}
if (c.back() < s) {
// vertex is at odd depth
if (t < c[1] || t > s) {
return c[0];
}
for (int i = sz - 1; i >= 1; i--) {
if (t > c[i]) {
return c[i];
}
}
} else {
if (t > c[sz - 2] || t < s) {
return c.back();
}
for (int i = 0; i < sz - 1; i++) {
if (t < c[i]) {
return c[i];
}
}
}
return -1;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<int> id(n);
vector<int> depth(n);
int cur = 0;
function<void(int, int)> dfs = [&](int src, int par) {
if (depth[src] % 2 == 0) {
id[src] = cur++;
}
for (int nxt: adj[src]) {
if (nxt == par) {
continue;
}
depth[nxt] = depth[src] + 1;
dfs(nxt, src);
}
if (depth[src] % 2 == 1) {
id[src] = cur++;
}
};
dfs(0, -1);
return id;
}
#ifdef LOCAL
int main() {
freopen("file.in", "r", stdin);
// string line; cin >> line;
int r;
cin >> r;
while (r--) {
int n, k;
cin >> n >> k;
vector<int> u(n);
vector<int> v(n);
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; i++ ){
cin >> u[i] >> v[i];
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<int> id = label(n, k, u, v);
int q; cin >> q;
while (q--) {
int z, y, w;
cin >> z >> y >> w;
vector<int> labels;
for (int nxt: adj[z]) {
labels.push_back(id[nxt]);
}
int v1 = find_next_station(id[z], id[y], labels);
int v2 = id[w];
assert(v1 == v2);
}
}
return 0;
}
#else
#endif
