Fedya is a seasoned traveller and is planning his trip to Treeland. Treeland is a country with an ancient road system which is in the form of a tree structure. $N$ cities of Treeland are numbered by $N$ positive integers: $1,2,3,\ldots,N$.

Fedya has not yet decided the starting point (city) of his journey and the cities he will visit. But there are a few things you know about Fedya's trip:

Fedya is fond of travelling to great distances. So if he is currently located in city $\mbox{V}$, his destination will be a city which is most distant from city $\mbox{V}$.

There might be more than 1 such cities. In that case, Fedya will choose a city that was already visited as less times as possible in this journey.

There still might be more than 1 such cities. In that case, Fedya will go to the city with the smallest number.

Fedya has prepared a list of $\mbox{M}$ possible journeys. Each one is characterized by two integers - the starting city $\mbox{V}$ and the total number of cities to be visited, $\mbox{K}$. For each of them, he is keen to know the total distance travelled by him.

Input Format

The first line of input will contain two space separated integers $N$ and $\mbox{M}$ - the number of cities and the number of possible journeys.

Then, there will be $(N-1)$ lines, each of them will contain two space separated integers $\mbox{X}$ $\mathbf{Y}$, denoting the bi-directional road between the cities with numbers $\mbox{X}$ and $\mathbf{Y}$ with the unitary length.

Then there will be $\mbox{M}$ lines, each of them will have two space separated integers $\mbox{V}$ and $\mbox{K}$, denoting a journey.

Constraints

$1\leq N,M\leq10^5$

$1\leq V,X,Y\leq N$

$1\leq K\leq10^9$

Output Format

For each journey, output the travelled distance on a separate line.

Sample Input
8 7
2 1
3 2
4 2
5 1
6 1
7 1
8 7
4 6
3 4
6 3
7 6
4 6
7 1
2 6

Sample Output

24
16
11
23
24
3
23

Explanation

The tree in question is given in the picture below. 

4 6 indicates that Fedya starts at 4. Now we see that the most distant city from 4 is 8. Fedya now travels to city 8.  From 8, the most distance cities are [4, 3]. As 4 is already visited, he chooses to visit city 3. From city 3, he revisits city 8 and so on. The cities in the order of visit is 4 - > 8 -> 3 -> 8 -> 4 -> 8 -> 3 which sums to 24. Hence, the answer.  
6 3 indicates that Fedya starts at city 6. From 6, the most distant cities are [3,4,8]. In this leg of the journey, no city is visited and hence Fedya chooses to visit the city with the smallest number 3. From 3, he visits 8 and then he ends his trip at city 4 which sums to 3 + 4 + 4 = 11. Hence, the answer.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Graph algorithms


Solutions:
DEBUG = 0

class CacheEntry(object):

	def __init__(self, f, d, n, a_f, a_d, a_n, excluded=None):
		self.f = f
		self.d = d
		self.n = n
		self.a_f = a_f
		self.a_d = a_d
		self.a_n = a_n
		self.excluded = excluded

	def complete(self, prev):
		return self.excluded is None or self.excluded == prev

	def furthest(self, prev):
		if self.excluded is None:
			if prev == self.n:
				return (self.a_f, self.a_d)
			else:
				return (self.f, self.d)
		elif self.excluded == prev:
			return (self.f, self.d)
		else:
			raise Exception('Failed')

	def update(self, f, d, n):
		if d > self.d:
			if n != self.n:
				(self.a_f, self.a_d, self.a_n) = (self.f, self.d, self.n)
			(self.f, self.d, self.n) = (f, d, n)
		elif d > self.a_d and n != self.n:
			(self.a_f, self.a_d, self.a_n) = (f, d, n)
		if n == self.excluded:
			self.excluded = None

	def __str__(self):
		return ' '.join(map(str, [self.f, self.d, self.n, self.a_f, self.a_d, self.a_n, self.excluded]))

class Cache(object):

	def __init__(self, tree):
		self.tree = tree
		self.data = dict()

	def finish(self, node, prev):
		missing = self.data[node].excluded
		if missing not in self.data or not self.data[missing].complete(node):
			return (False, [(missing, node)])
		else:
			(f, d) = self.data[missing].furthest(node)
			self.data[node].update(f, d + 1, missing)
			return (True, self.data[node].furthest(prev))

	def construct(self, node, prev):
		c = CacheEntry(node, 0, node, 0, 0, 0, excluded=prev)
		for child in self.tree[node]:
			if child == prev:
				continue
			(f, d) = self.data[child].furthest(node)
			c.update(f, d + 1, child)
		return c

	def furthest(self, node, prev=None):
		if node in self.data:
			if self.data[node].complete(prev):
				return (True, self.data[node].furthest(prev))
			else:
				return self.finish(node, prev)
		else:
			req = [(child, node) for child in self.tree[node] if child != prev and (child not in self.data or not self.data[child].complete(node))]
			if req:
				return (False, req)
			self.data[node] = self.construct(node, prev)
			return (True, self.data[node].furthest(prev))

	def __str__(self):
		return '\n'.join(('{}--- {}'.format(key, str(self.data[key])) for key in sorted(self.data.keys())))

def longest_f(tree):
	cache = Cache(tree)

	def longest(origin):
		(ok, ret) = cache.furthest(origin)
		if DEBUG > 1:
			print('Finding longest from', origin)
			print('Called furthest origin')
			print('origin:', origin)
			print('ok, ret:', ok, ret)
			if ok:
				print(cache.data[origin])
			print('--------------------')
		if ok:
			return ret
		original_origin = origin
		stack = ret
		while stack:
			(origin, prev) = stack[-1]
			(ok, ret) = cache.furthest(origin, prev)
			if DEBUG > 1:
				print('Called furthest_prev')
				print('origin:', origin)
				print('prev:', prev)
				print('ok, ret:', ok, ret)
				if ok:
					print(cache.data[origin])
				print('--------------------')
			if ok:
				stack.pop()
			else:
				stack += ret
		(ok, ret) = cache.furthest(original_origin)
		if DEBUG > 1:
			print('Called furthest origin')
			print('original_origin:', original_origin)
			print('ok, ret:', ok, ret)
			if ok:
				print(cache.data[original_origin])
			print('--------------------')
		if not ok:
			raise Exception('Failed to find all necessary information')
			print(ret)
		return ret

	def print_cache():
		print(cache)
	return (longest, print_cache)

def distance(longest_f, v, k):
	ki = 0
	journeys = []
	distance = 0
	while ki < k:
		(v, d) = longest_f(v)
		journeys.append(d)
		distance += d
		ki += 1
		if len(journeys) >= 3 and all((journey == journeys[-1] for journey in journeys[-3:])):
			distance += (k - ki) * journeys[-1]
			if DEBUG:
				print('Skipping from journeys {} to total_distance of {}'.format(journeys, distance))
			break
	return distance

def add_edge(x, y):
	if tree[x] is None:
		tree[x] = [y]
	else:
		tree[x].append(y)
import sys
if len(sys.argv) > 1:
	f = open(sys.argv[1])

	def input():
		return next(f)
	try:
		u = int(sys.argv[-1])
	except:
		u = 0
(n, m) = [int(x) for x in input().split()]
tree = [None] * (n + 1)
for _ in range(n - 1):
	(x, y) = [int(x) for x in input().split()]
	add_edge(x, y)
	add_edge(y, x)
if DEBUG:
	print('tree:', tree)
(longest, pc) = longest_f(tree)
for _ in range(m):
	(v, k) = [int(x) for x in input().split()]
	if DEBUG:
		print('v, k:', v, k)
	print(distance(longest, v, k))
if DEBUG:
	pc()


from collections import defaultdict, deque

def get_farthest(city, citymap):
	max_distance = 0
	farthest_city = city
	distance = 0
	queue = deque()
	queue.append((city, 0))
	visited = set([city])
	while len(queue) > 0:
		(current_city, distance) = queue.pop()
		if distance > max_distance:
			max_distance = distance
			farthest_city = current_city
		candidates = citymap[current_city]
		for city in candidates:
			if city in visited:
				continue
			visited.add(city)
			queue.append((city, distance + 1))
	return (farthest_city, max_distance)

def get_distances(city, citymap):
	distances = {city: 0}
	queue = deque()
	queue.append((city, 0))
	visited = set([city])
	while len(queue) > 0:
		(current_city, distance) = queue.pop()
		distances[current_city] = distance
		candidates = citymap[current_city]
		for city in candidates:
			if city in visited:
				continue
			visited.add(city)
			queue.append((city, distance + 1))
	return distances
(num_of_connections, num_of_journeys) = map(int, input().strip().split(' '))
citymap = defaultdict(list)
arbitrary_city = None
for i in range(num_of_connections - 1):
	(city_from, city_to) = map(int, input().strip().split(' '))
	citymap[city_from].append(city_to)
	citymap[city_to].append(city_from)
	arbitrary_city = city_from
(farthest_one_city, _) = get_farthest(arbitrary_city, citymap)
(farthest_two_city, max_distance) = get_farthest(farthest_one_city, citymap)
distances_to_one_city = get_distances(farthest_one_city, citymap)
distances_to_two_city = get_distances(farthest_two_city, citymap)
results = []
for i in range(num_of_journeys):
	(start_city, steps) = map(int, input().strip().split(' '))
	distance = max(distances_to_one_city[start_city], distances_to_two_city[start_city]) + (steps - 1) * max_distance
	results.append(distance)
print(*map(str, results), sep='\n')


from collections import defaultdict as ddict, deque
(n, m) = map(int, input().split())
roads = []
for _ in range(n - 1):
	roads.append(list(map(int, input().rstrip().split())))
journeys = []
for _ in range(m):
	journeys.append(list(map(int, input().rstrip().split())))
graph = ddict(set)
for (i, j) in roads:
	graph[i - 1].add(j - 1)
	graph[j - 1].add(i - 1)

def bfs(node):
	queue = deque([node])
	d = [-1] * n
	d[node] = 0
	while queue:
		last = queue.popleft()
		for i in graph[last]:
			if d[i] < 0:
				d[i] = d[last] + 1
				queue.append(i)
	return (d, last)
(_, last) = bfs(0)
(dis1, last) = bfs(last)
(dis2, last) = bfs(last)
dis = [max(i) for i in zip(dis1, dis2)]
diameter = max(dis)
for (node, k) in journeys:
	print((k - 1) * diameter + dis[node - 1])


class Graph(object):

	def __init__(self, n):
		self.adj_list = {}
		self.dim = n

	def add_edge(self, x, y):

		def add_one_direction(x, y):
			try:
				self.adj_list[x].append(y)
			except KeyError:
				self.adj_list[x] = [y]
		add_one_direction(x, y)
		add_one_direction(y, x)

	def bfs(self, start):
		cur_lvl = [start]
		dist = [None] * self.dim
		dist[start] = 0
		local_max_val = None
		local_max_idx = None
		while cur_lvl:
			vertex = cur_lvl.pop()
			for neighbor in self.adj_list[vertex]:
				if dist[neighbor] is not None:
					continue
				dist[neighbor] = dist[vertex] + 1
				cur_lvl.append(neighbor)
				if local_max_val is None or local_max_val < dist[neighbor]:
					local_max_val = dist[neighbor]
					local_max_idx = neighbor
		return (dist, local_max_idx)

def main():
	(n, m) = map(int, input().split())
	graph = Graph(n)
	for _ in range(n - 1):
		(x, y) = map(lambda x: int(x) - 1, input().split())
		graph.add_edge(x, y)
	(_, oscillation_point1) = graph.bfs(0)
	(dist1, oscillation_point2) = graph.bfs(oscillation_point1)
	(dist2, _) = graph.bfs(oscillation_point2)
	for _ in range(m):
		(v, k) = map(int, input().split())
		v -= 1
		first_travel = max(dist1[v], dist2[v])
		rest_travel = (k - 1) * dist1[oscillation_point2]
		print(first_travel + rest_travel)
main()


(N, M) = map(int, input().split(' '))

class Node:
	__slots__ = ['id', 'e', 'l', 'el', 'ec', 'p']

	def __init__(self, id):
		self.id = id
		self.e = []
		self.l = -1
		self.el = 0
		self.ec = 0
		self.p = None
NODES = [Node(id) for id in range(N + 1)]
S = [None] * N

def init():
	i = 1
	while i < N:
		(a, b) = map(int, input().split(' '))
		NODES[a].e.append(NODES[b])
		NODES[b].e.append(NODES[a])
		i += 1

def findCenter():
	SP = 0
	EP = 0
	i = 1
	while i <= N:
		ni = NODES[i]
		ni.el = len(ni.e)
		if ni.el == 1:
			S[SP] = ni
			SP += 1
		i += 1
	while True:
		s = S[EP]
		EP += 1
		if s.ec == s.el - 1:
			mt = 0
			k = 1
			while k < s.el:
				ek = s.e[k]
				if ek.l == -1:
					(s.e[0], s.e[k]) = (s.e[k], s.e[0])
				if s.e[k].l > mt:
					mt = s.e[k].l
				k += 1
			s.l = mt + 1
			s.p = s.e[0]
			s.p.ec += 1
			if s.p.ec == s.p.el - 1:
				S[SP] = s.p
				SP += 1
		elif s.ec == s.el:
			mt = 0
			k = 0
			mtc = 0
			while k < s.el:
				ek = s.e[k]
				if s.e[k].l > mt:
					mt = s.e[k].l
					mtc = 1
				elif s.e[k].l == mt:
					mtc += 1
				k += 1
			break
	RA = S[-2].l
	FN = RA * 2
	S[-1].l = 0
	i = N - 2
	if mtc == 1:
		i -= 1
		S[-2].l = 0
		S[-2].p = None
		FN -= 1
		RA -= 1
	while i >= 0:
		S[i].l = S[i].p.l + 1
		i -= 1
	return (RA, FN)
init()
(RA, FN) = findCenter()
F = [-1] * (N + 1)
i = 0
while i < M:
	(v, k) = map(int, input().split(' '))
	print(k * FN - RA + NODES[v].l)
	i += 1


DEBUG = 0

class CacheEntry(object):

	def __init__(self, f, d, n, a_f, a_d, a_n, excluded=None):
		self.f = f
		self.d = d
		self.n = n
		self.a_f = a_f
		self.a_d = a_d
		self.a_n = a_n
		self.excluded = excluded

	def complete(self, prev):
		return self.excluded is None or self.excluded == prev

	def furthest(self, prev):
		if self.excluded is None:
			if prev == self.n:
				return (self.a_f, self.a_d)
			else:
				return (self.f, self.d)
		elif self.excluded == prev:
			return (self.f, self.d)
		else:
			raise Exception('Failed')

	def update(self, f, d, n):
		if d > self.d:
			if n != self.n:
				(self.a_f, self.a_d, self.a_n) = (self.f, self.d, self.n)
			(self.f, self.d, self.n) = (f, d, n)
		elif d > self.a_d and n != self.n:
			(self.a_f, self.a_d, self.a_n) = (f, d, n)
		if n == self.excluded:
			self.excluded = None

	def __str__(self):
		return ' '.join(map(str, [self.f, self.d, self.n, self.a_f, self.a_d, self.a_n, self.excluded]))

class Cache(object):

	def __init__(self, tree):
		self.tree = tree
		self.data = dict()

	def finish(self, node, prev):
		missing = self.data[node].excluded
		if missing not in self.data or not self.data[missing].complete(node):
			return (False, [(missing, node)])
		else:
			(f, d) = self.data[missing].furthest(node)
			self.data[node].update(f, d + 1, missing)
			return (True, self.data[node].furthest(prev))

	def construct(self, node, prev):
		c = CacheEntry(node, 0, node, 0, 0, 0, excluded=prev)
		for child in self.tree[node]:
			if child == prev:
				continue
			(f, d) = self.data[child].furthest(node)
			c.update(f, d + 1, child)
		return c

	def furthest(self, node, prev=None):
		if node in self.data:
			if self.data[node].complete(prev):
				return (True, self.data[node].furthest(prev))
			else:
				return self.finish(node, prev)
		else:
			req = [(child, node) for child in self.tree[node] if child != prev and (child not in self.data or not self.data[child].complete(node))]
			if req:
				return (False, req)
			self.data[node] = self.construct(node, prev)
			return (True, self.data[node].furthest(prev))

	def __str__(self):
		return '\n'.join(('{}--- {}'.format(key, str(self.data[key])) for key in sorted(self.data.keys())))

def longest_f(tree):
	cache = Cache(tree)

	def longest(origin):
		(ok, ret) = cache.furthest(origin)
		if DEBUG > 1:
			print('Finding longest from', origin)
			print('Called furthest origin')
			print('origin:', origin)
			print('ok, ret:', ok, ret)
			if ok:
				print(cache.data[origin])
			print('--------------------')
		if ok:
			return ret
		original_origin = origin
		stack = ret
		while stack:
			(origin, prev) = stack[-1]
			(ok, ret) = cache.furthest(origin, prev)
			if DEBUG > 1:
				print('Called furthest_prev')
				print('origin:', origin)
				print('prev:', prev)
				print('ok, ret:', ok, ret)
				if ok:
					print(cache.data[origin])
				print('--------------------')
			if ok:
				stack.pop()
			else:
				stack += ret
		(ok, ret) = cache.furthest(original_origin)
		if DEBUG > 1:
			print('Called furthest origin')
			print('original_origin:', original_origin)
			print('ok, ret:', ok, ret)
			if ok:
				print(cache.data[original_origin])
			print('--------------------')
		if not ok:
			raise Exception('Failed to find all necessary information')
			print(ret)
		return ret

	def print_cache():
		print(cache)
	return (longest, print_cache)

def distance(longest_f, v, k):
	ki = 0
	journeys = []
	distance = 0
	while ki < k:
		(v, d) = longest_f(v)
		journeys.append(d)
		distance += d
		ki += 1
		if len(journeys) >= 3 and all((journey == journeys[-1] for journey in journeys[-3:])):
			distance += (k - ki) * journeys[-1]
			if DEBUG:
				print('Skipping from journeys {} to total_distance of {}'.format(journeys, distance))
			break
	return distance

def add_edge(x, y):
	if tree[x] is None:
		tree[x] = [y]
	else:
		tree[x].append(y)
import sys
if len(sys.argv) > 1:
	f = open(sys.argv[1])

	def input():
		return next(f)
	try:
		u = int(sys.argv[-1])
	except:
		u = 0
(n, m) = [int(x) for x in input().split()]
tree = [None] * (n + 1)
for _ in range(n - 1):
	(x, y) = [int(x) for x in input().split()]
	add_edge(x, y)
	add_edge(y, x)
if DEBUG:
	print('tree:', tree)
(longest, pc) = longest_f(tree)
for _ in range(m):
	(v, k) = [int(x) for x in input().split()]
	if DEBUG:
		print('v, k:', v, k)
	print(distance(longest, v, k))
if DEBUG:
	pc()


import os
import sys
from collections import defaultdict, deque

def get_farthest(city, citymap):
	max_distance = 0
	farthest_city = city
	distance = 0
	queue = deque()
	queue.append((city, 0))
	visited = set([city])
	while len(queue) > 0:
		(current_city, distance) = queue.pop()
		if distance > max_distance:
			max_distance = distance
			farthest_city = current_city
		candidates = citymap[current_city]
		for city in candidates:
			if city in visited:
				continue
			visited.add(city)
			queue.append((city, distance + 1))
	return (farthest_city, max_distance)

def get_distances(city, citymap):
	distances = {city: 0}
	queue = deque()
	queue.append((city, 0))
	visited = set([city])
	while len(queue) > 0:
		(current_city, distance) = queue.pop()
		distances[current_city] = distance
		candidates = citymap[current_city]
		for city in candidates:
			if city in visited:
				continue
			visited.add(city)
			queue.append((city, distance + 1))
	return distances
(num_of_connections, num_of_journeys) = map(int, input().strip().split(' '))
citymap = defaultdict(list)
arbitrary_city = None
for i in range(num_of_connections - 1):
	(city_from, city_to) = map(int, input().strip().split(' '))
	citymap[city_from].append(city_to)
	citymap[city_to].append(city_from)
	arbitrary_city = city_from
(farthest_one_city, _) = get_farthest(arbitrary_city, citymap)
(farthest_two_city, max_distance) = get_farthest(farthest_one_city, citymap)
distances_to_one_city = get_distances(farthest_one_city, citymap)
distances_to_two_city = get_distances(farthest_two_city, citymap)
results = []
for i in range(num_of_journeys):
	(start_city, steps) = map(int, input().strip().split(' '))
	distance = max(distances_to_one_city[start_city], distances_to_two_city[start_city]) + (steps - 1) * max_distance
	results.append(distance)
print(*map(str, results), sep='\n')