#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (k); i >= (j); i--)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using VI = std::vector<int>;
using ll = long long;
using PII = std::pair<int, int>;
using db = double;
using namespace std;

const int LOGN = 12, N = 3010;

int n, m, dep[N], p[N][13], d1[N], d2[N];
VI adj[N];

void dfs(int u, int f = 0) {
	p[u][0] = f;
	dep[u] = dep[f] + 1;
	for (auto v : adj[u]) if (v != f) {
		dfs(v, u);
	}
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	per(i, 0, LOGN) if (dep[p[v][i]] >= dep[u]) v = p[v][i];
	if (u == v) return u;
	per(i ,0 ,LOGN) if (p[v][i] != p[u][i]) u = p[u][i], v = p[v][i];
	return p[u][0];
}

ll exgcd(ll a, ll b, ll &x, ll &y) {
	if (!b) {
		x = 1; y = 0;
		return a;
	}
	ll z, d;
	d = exgcd(b, a % b, z, x);
	y = z - a / b * x;
	return d;
}

ll excrt(ll m1, ll r1, ll m2, ll r2) {
	ll w = r2 - r1;
	ll x, y;
	ll d = exgcd(m1, m2, x, y);
	if (w % d) return 1e18;
	w /= d;
	ll rmod = m2 / d;
	x = (x * w % rmod + rmod) % rmod;
	r1 += x * m1;
	m1 *= rmod;
	return r1;
}

void solve() {
	cin >> n >> m;
	rep(i, 1, n) adj[i].clear();
	rep(i, 1, n - 1) {
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	dfs(1);

	rep(j, 1, LOGN) {
		rep(i, 1, n) {
			p[i][j] = p[p[i][j - 1]][j - 1];
		}
	}

	auto get = [&](int s, int t) {
		int w = lca(s, t);
		vector<int> up, down;
		while (s != w) {
			up.pb(s);
			s = p[s][0];
		}
		up.pb(w);
		while (t != w) {
			down.pb(t);
			t = p[t][0];
		}
		reverse(all(down));
		for (auto v : down) up.pb(v);
		return up;
	};

	rep(_, 1, m) {
		int s1, t1, s2, t2;
		cin >> s1 >> t1 >> s2 >> t2;
		auto p1 = get(s1, t1), p2 = get(s2, t2);
		int dd = 0;
		rep(i, 1, n) d1[i] = d2[i] = -1;
		for (auto v : p1) {
			d1[v] = dd++;
		}
		dd = 0;
		for (auto v : p2) {
			d2[v] = dd++;
		}
		int M1 = 2 * (SZ(p1) - 1), M2 = 2 * (SZ(p2) - 1);
		int ans = -1;
		ll anst = 1e18;
		rep(i, 1, n) if (~d1[i] && ~d2[i]) {
			for (auto x : {M1 - d1[i], d1[i]}) {
				for (auto y : {M2 - d2[i], d2[i]}) {
					ll t = excrt(M1, x % M1, M2, y % M2);
					// cerr << "eq : " << x % M1 << " " << M1 << " " << y % M2 << " " << M2 << "\n";
					// cerr << "ff : " << i << " " << t << "\n";
					if (t < anst) {
						anst = t;
						ans = i;
					//	cerr << "ff : " << i << "\n";
					}
				}
			}
		}
		cout << ans << "\n";
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}