Read problems statements in Mandarin Chinese. 

In a rooted tree, the  (or LCA for short) of two vertices u and v is defined as the lowest vertex that is ancestor of both that two vertices.

Given a tree of N vertices, you need to answer the question of the form "r u v" which means if the root of the tree is at r then what is LCA of u and v.
 
------ Input ------ 

The first line contains a single integer N. Each line in the next N - 1 lines contains a pair of integer u and v representing a edge between this two vertices.

The next line contains a single integer Q which is the number of the queries. Each line in the next Q lines contains three integers  r, u, v representing a query.
 
------ Output ------ 

For each query, write out the answer on a single line.

------ Constraints ------ 

20 points:

1 ≤ N, Q ≤ 100

40 points:

1 ≤ N, Q ≤ 10^{5}
There is less than 10 unique value of r in all queries

40 points:

1 ≤ N, Q ≤ 2 × 10^{5}

------ Example ------ 

Input:
4
1 2
2 3
1 4
2
1 4 2
2 4 2

Output:
1
2

------ Explanation ------ 

"1 4 2": if 1 is the root, it is parent of both 2 and 4 so LCA of 2 and 4 is 1.
"2 4 2": the root of the tree is at 2, according to the definition, LCA of any vertex with 2 is 2.

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Range queries

Tree algorithms

Data structures

Tree queries
Skill types: Data structures

Range queries

Starter code:

Solutions:
from math import log2

def dfs(s, p, l):
	stack = [s]
	p[s] = s
	l[s] = 1
	while stack:
		x = stack.pop()
		for y in Tree[x]:
			if not l[y]:
				p[y] = x
				l[y] = l[x] + 1
				stack.append(y)

def searchLCA(x, y):
	if l[x] > l[y]:
		(x, y) = (y, x)
	d = l[y] - l[x]
	if d != 0:
		for i in range(MAX2 - 1, -1, -1):
			if d >= 1 << i:
				d -= 1 << i
				y = pp[y][i]
	if x == y:
		return x + 1
	for i in range(MAX2 - 1, -1, -1):
		if pp[x][i] != pp[y][i]:
			x = pp[x][i]
			y = pp[y][i]
	return pp[x][0] + 1
N = int(input())
Tree = [[] for _ in range(N)]
for _ in range(N - 1):
	(x, y) = map(int, input().split())
	Tree[x - 1].append(y - 1)
	Tree[y - 1].append(x - 1)
p = [None] * N
l = [None] * N
dfs(0, p, l)
MAX2 = int(log2(max(l))) + 1
pp = [[None] * MAX2 for _ in range(N)]
for i in range(N):
	pp[i][0] = p[i]
for j in range(1, MAX2):
	for i in range(N):
		pp[i][j] = pp[pp[i][j - 1]][j - 1]
Q = int(input())
for _ in range(Q):
	(r, x, y) = map(int, input().split())
	rr = searchLCA(x - 1, y - 1)
	xx = searchLCA(r - 1, y - 1)
	yy = searchLCA(x - 1, r - 1)
	if xx == yy:
		print(rr)
	elif xx == rr:
		print(yy)
	else:
		print(xx)


from sys import stdin, stdout
import sys
from math import log2
sys.setrecursionlimit(10000000)
I = stdin.readline
n = int(I())
grph = {}

def dfs(grph, n, vis, par, st, lvl, p=-1):
	par[st] = p
	vis[st] = 1
	if p == -1:
		lvl[st] = 0
	else:
		lvl[st] = lvl[p] + 1
	for i in grph[st]:
		if vis[i] == -1:
			dfs(grph, n, vis, par, i, lvl, st)

def lca(bit, lvl, x, y, log):
	if lvl[x] < lvl[y]:
		(x, y) = (y, x)
	var = x
	diff = lvl[x] - lvl[y]
	while diff > 0:
		ln2 = int(log2(diff))
		var = bit[var][ln2]
		diff -= 1 << ln2
	for i in range(log):
		if bit[var][i] != bit[y][i]:
			var = bit[var][i]
			y = bit[y][i]
		else:
			break
	while var != y:
		var = bit[var][0]
		y = bit[y][0]
	return var
for i in range(n - 1):
	(u, v) = map(int, I().split())
	if u in grph:
		grph[u].append(v)
	else:
		grph[u] = [v]
	if v in grph:
		grph[v].append(u)
	else:
		grph[v] = [u]
vis = {i: -1 for i in grph.keys()}
par = {}
key = list(grph.keys())
lvl = {}
dfs(grph, n, vis, par, key[0], lvl)
ht = max(lvl.values()) + 1
bit = {i: [] for i in key}
log = 0
var = ht
while var > 1:
	log += 1
	var //= 2
for i in range(log + 1):
	for j in key:
		if i == 0:
			bit[j].append(par[j])
		elif bit[j][-1] == -1:
			bit[j].append(-1)
		else:
			bit[j].append(bit[bit[j][i - 1]][i - 1])
for i in range(int(I())):
	(r, u, v) = map(int, I().split())
	(a, b, c) = (lca(bit, lvl, u, v, log + 1), lca(bit, lvl, r, u, log + 1), lca(bit, lvl, r, v, log + 1))
	if a == b:
		print(c)
	elif b == c:
		print(a)
	else:
		print(b)


from math import inf
from collections import namedtuple

class SegmentTree:

	def __init__(self, arr):
		self.N = len(arr)
		self.st = [(inf, inf) for _ in range(2 * self.N)]
		for (i, v) in enumerate(arr):
			self.st[i + self.N] = arr[i]
		for i in range(self.N - 1, 0, -1):
			self.st[i] = min(self.st[i << 1], self.st[i << 1 | 1])

	def query(self, left, right):
		result = (inf, inf)
		left += self.N
		right += self.N
		while left < right:
			if left & 1:
				result = min(result, self.st[left])
				left += 1
			if right & 1:
				right -= 1
				result = min(result, self.st[right])
			left >>= 1
			right >>= 1
		return result[1]

class Tree:

	def __init__(self, root, adj):
		self.root = root
		self.euler = [(inf, inf) for _ in range(2 * len(adj))]
		self.euler_start = [0 for _ in adj]
		self.dfs(root, -1, 0, adj)
		self.st = SegmentTree(self.euler)

	def dfs(self, node, parent, height, adj):
		self.euler_start[node] = len(self.euler)
		self.euler.append((height, node))
		for neighbor in adj[node]:
			if neighbor != parent:
				self.dfs(neighbor, node, height + 1, adj)
				self.euler.append((height, node))

	def query_lca(self, u, v):
		(left, right) = (self.euler_start[u], self.euler_start[v])
		if left > right:
			(left, right) = (right, left)
		return self.st.query(left, right + 1)
Query = namedtuple('Query', ['id', 'root', 'u', 'v'])

def main():
	import sys
	sys.setrecursionlimit(pow(10, 9))
	node_count = int(sys.stdin.readline())
	adj = [[] for _ in range(node_count + 1)]
	for _ in range(node_count - 1):
		(u, v) = (int(i) for i in sys.stdin.readline().split())
		adj[u].append(v)
		adj[v].append(u)
	query_count = int(sys.stdin.readline())
	queries = []
	tree = Tree(1, adj)
	for q in range(query_count):
		(root, u, v) = (int(i) for i in sys.stdin.readline().split())
		a = tree.query_lca(root, u)
		b = tree.query_lca(root, v)
		c = tree.query_lca(u, v)
		if a == b == c:
			print(a)
		elif a == b:
			print(c)
		elif a == c:
			print(b)
		elif b == c:
			print(a)
main()