You are given an unweighted tree with N$N$ nodes (numbered 1$1$ through N$N$). Let's denote the distance between any two nodes p$p$ and q$q$ by d(p,q)$d(p, q)$.
You should answer Q$Q$ queries. In each query, you are given parameters a$a$, da$d_a$, b$b$, db$d_b$, and you should find a node x$x$ such that d(x,a)=da$d(x, a) = d_a$ and d(x,b)=db$d(x, b) = d_b$, or determine that there is no such node.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains two space-separated integers N$N$ and Q$Q$.
- Each of the next N−1$N-1$ lines contains two space-separated integers u$u$ and v$v$ denoting that nodes u$u$ and v$v$ are connected by an edge.
- Each of the next Q$Q$ lines contains four space-separated integers a$a$, da$d_a$, b$b$ and db$d_b$ describing a query.

-----Output-----
For each query, print a single line containing one integer ― the number of a node satisfying the given requirements, or −1$-1$ if no such node exists.
If there are multiple solutions, you may output any one.

-----Constraints-----
- 1≤T≤1,000$1 \le T \le 1,000$
- 1≤N,Q≤106$1 \le N, Q \le 10^6$
- 1≤u,v≤N$1 \le u, v \le N$
- the graph on the input is a tree
- 1≤a,b≤N$1 \le a, b \le N$
- 1≤da,db<N$1 \le d_a, d_b < N$
- the sum of N$N$ over all test cases does not exceed 106$10^6$
- the sum of Q$Q$ over all test cases does not exceed 106$10^6$

-----Subtasks-----
Subtask #1 (50 points):
- 1≤N,Q≤1,000$1 \le N, Q \le 1,000$
- the sum of N$N$ over all test cases does not exceed 1,000$1,000$
- the sum of Q$Q$ over all test cases does not exceed 1,000$1,000$
Subtask #2 (50 points): original constraints

-----Example Input-----
1
5 3
1 2
2 3
3 4
3 5
2 1 4 1
2 2 4 2
1 1 2 1

-----Example Output-----
3
5
-1

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
class TestCase:

	def __init__(self):
		[self.node_count, self.query_count] = read_line()

	def fill_nodes(self):
		self.nodes = {n + 1: [] for n in range(self.node_count)}
		for i in range(self.node_count - 1):
			(new_node_1, new_node_2) = read_line()
			self.nodes[new_node_1].append(new_node_2)
			self.nodes[new_node_2].append(new_node_1)

	def resolve_query(self, query):
		(a, d_a, b, d_b) = query
		suiting_a = self.find_nodes_with_distance(a, d_a)
		suiting_b = self.find_nodes_with_distance(b, d_b)
		fitting = [node for node in suiting_a if node in suiting_b]
		if len(fitting) == 0:
			return -1
		else:
			return fitting[0]

	def find_nodes_with_distance(self, start_node, distance):
		from_nodes = {start_node}
		passed_nodes = from_nodes
		for i in range(distance):
			to_nodes = set()
			for node in from_nodes:
				to_nodes.update(self.nodes[node])
			for node in passed_nodes:
				if node in to_nodes:
					to_nodes.remove(node)
			passed_nodes.update(to_nodes)
			from_nodes = to_nodes
		return list(from_nodes)

def read_line():
	line = input()
	return [int(s) for s in line.split(' ')]
num_testcases = int(input())
for i in range(num_testcases):
	testcase = TestCase()
	testcase.fill_nodes()
	for q in range(testcase.query_count):
		query = read_line()
		print(testcase.resolve_query(query))


def bfs(tr, sp, d):
	temp = [sp]
	vl = [-1] * len(tr)
	vl[sp] = 0
	while len(temp) > 0:
		z = temp.pop(0)
		if vl[z] >= d:
			continue
		for e in tr[z]:
			if vl[e] == -1:
				vl[e] = vl[z] + 1
				temp.append(e)
	return [i for i in range(len(vl)) if vl[i] == d]

def myfunc():
	(n, q) = list(map(int, input().split()))
	tr = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = list(map(int, input().split()))
		tr[u].append(v)
		tr[v].append(u)
	for qn in range(q):
		(a, da, b, db) = list(map(int, input().split()))
		ta = set(bfs(tr, a, da))
		tb = set(bfs(tr, b, db))
		x = list(ta.intersection(tb))
		if len(x) > 0:
			print(x[0])
		else:
			print(-1)
t = int(input())
for _ in range(t):
	myfunc()


t = int(input().strip())
result = []

class Distance:

	def __init__(self, n, dist):
		self.n = n
		self.dist = dist

	def cal_dist(self, u, v):
		self.dist[u][v] = self.dist[v][u] = 1
		for i in range(n):
			if self.dist[u][i] != -1 and self.dist[v][i] == -1 and (i != u) and (i != v):
				self.dist[v][i] = self.dist[i][v] = self.dist[u][i] + 1
		for i in range(n):
			if self.dist[v][i] != -1 and self.dist[u][i] == -1 and (i != u) and (i != v):
				self.dist[u][i] = self.dist[i][u] = self.dist[v][i] + 1

	def return_dist(self):
		return self.dist
for i in range(t):
	(n, q) = map(int, input().strip().split())
	dist = [[-1 for j in range(n)] for k in range(n)]
	for j in range(n):
		dist[j][j] = 0
	d = Distance(n, dist)
	for j in range(n - 1):
		(u, v) = map(int, input().strip().split())
		d.cal_dist(u - 1, v - 1)
	dist = d.return_dist()
	for j in range(q):
		(a, da, b, db) = map(int, input().strip().split())
		ans = -1
		for k in range(n):
			if dist[a - 1][k] == da and dist[b - 1][k] == db:
				ans = k + 1
				break
		result.append(ans)
print(*result, sep='\n')


try:
	t = int(input())
	for __ in range(t):
		(N, m) = map(int, input().split())
		A = []
		dic = {}
		for i in range(N - 1):
			(a, b) = map(int, input().split())
			if a in dic:
				dic[a] += str(b) + ','
			else:
				dic[a] = str(b) + ','
			if b in dic:
				dic[b] += str(a) + ','
			else:
				dic[b] = str(a) + ','
		for _ in range(m):
			(term1, dist1, term2, dist2) = map(str, input().split())
			l = [term1]
			A = []

			def distance(t, c, x, A, l):
				if t == int(c):
					A += [x]
				else:
					string = ''
					for i in dic[int(x)]:
						if i == ',':
							if string not in l:
								l += [string]
								x = string
								distance(t + 1, c, x, A, l)
								string = ''
							else:
								string = ''
						else:
							string += str(i)
			distance(0, dist1, term1, A, l)
			l1 = []
			for i in A:
				if i != term1:
					l1 += [i]
			A = []
			l = [term2]
			distance(0, dist2, term2, A, l)
			l2 = []
			for i in A:
				if i != term2:
					l2 += [i]
			count = 0
			for i in l1:
				if i in l2:
					if count < 1:
						print(int(i))
						count += 1
			if count == 0:
				print(-1)
except:
	pass


def dist(a, b):
	if (a, b) in di:
		return di[a, b]
	if distance[a] < distance[b]:
		(a, b) = (b, a)
	c = distance[a] - distance[b]
	l = []
	t = a
	while c:
		l.append(t)
		t = p[t]
		c -= 1
	w = b
	r = []
	while t != w:
		l.append(t)
		r.append(w)
		t = p[t]
		w = p[w]
	for i in l:
		for j in r:
			di[i, j] = distance[i] + distance[j] - 2 * distance[t]
	di[a, b] = distance[a] + distance[b] - 2 * distance[t]
	return di[a, b]
t = int(input())
for t_iter in range(t):
	(n, q) = map(int, input().split())
	g = {}
	for i in range(n):
		g[i] = []
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	p = [None] * n
	distance = [-1] * n
	distance[0] = 0
	qu = [0]
	while len(qu):
		u = qu.pop(0)
		for v in g[u]:
			if distance[v] == -1:
				distance[v] = distance[u] + 1
				p[v] = u
				qu.append(v)
	di = {}
	for q_iter in range(q):
		(a, da, b, db) = map(int, input().split())
		a -= 1
		b -= 1
		flag = 0
		for i in range(n):
			if dist(a, i) == da and dist(b, i) == db:
				print(i + 1)
				flag = 1
				break
		if flag == 0:
			print(-1)


import numpy as np

def add(adj, a, b, n):
	adj[a, b] = adj[b, a] = 1
	for i in range(n):
		if adj[a, i] != -10 and a != i and (b != i) and (adj[b, i] == -10):
			adj[b, i] = adj[a, i] + 1
			adj[i, b] = adj[b, i]
	for i in range(n):
		if adj[b, i] != -10 and b != i and (a != i) and (adj[a, i] == -10):
			adj[a, i] = adj[b, i] + 1
			adj[i, a] = adj[a, i]
	return adj
t = int(input())
while t > 0:
	(n, q) = map(int, input().split())
	adj = np.zeros((n, n), dtype='int')
	adj += np.array([-10])
	for i in range(n):
		adj[i, i] = 0
	for i in range(1, n):
		(a, b) = map(int, input().split())
		adj = add(adj, a - 1, b - 1, n)
	for _ in range(q):
		(a, da, b, db) = map(int, input().split())
		x = -1
		for i in range(n):
			if adj[a - 1, i] == da and adj[b - 1, i] == db:
				x = i + 1
				break
		print(x)
	t -= 1