You are given an unweighted tree with n vertices. Then n - 1 following operations are applied to the tree. A single operation consists of the following steps:   choose two leaves;  add the length of the simple path between them to the answer;  remove one of the chosen leaves from the tree. 

Initial answer (before applying operations) is 0. Obviously after n - 1 such operations the tree will consist of a single vertex. 

Calculate the maximal possible answer you can achieve, and construct a sequence of operations that allows you to achieve this answer!


-----Input-----

The first line contains one integer number n (2 ≤ n ≤ 2·10^5) — the number of vertices in the tree. 

Next n - 1 lines describe the edges of the tree in form a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}). It is guaranteed that given graph is a tree.


-----Output-----

In the first line print one integer number — maximal possible answer. 

In the next n - 1 lines print the operations in order of their applying in format a_{i}, b_{i}, c_{i}, where a_{i}, b_{i} — pair of the leaves that are chosen in the current operation (1 ≤ a_{i}, b_{i} ≤ n), c_{i} (1 ≤ c_{i} ≤ n, c_{i} = a_{i} or c_{i} = b_{i}) — choosen leaf that is removed from the tree in the current operation. 

See the examples for better understanding.


-----Examples-----
Input
3
1 2
1 3

Output
3
2 3 3
2 1 1

Input
5
1 2
1 3
2 4
2 5

Output
9
3 5 5
4 3 3
4 1 1
4 2 2

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Greedy algorithms

Tree algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
n = int(sys.stdin.buffer.readline().decode('utf-8'))
adj = [[] for _ in range(n)]
deg = [0] * n
for (u, v) in (map(int, line.decode('utf-8').split()) for line in sys.stdin.buffer):
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
	deg[u - 1] += 1
	deg[v - 1] += 1

def get_dia(adj):
	from collections import deque
	n = len(adj)
	dq = deque([(0, -1)])
	while dq:
		(end1, par) = dq.popleft()
		for dest in adj[end1]:
			if dest != par:
				dq.append((dest, end1))
	prev = [-1] * n
	prev[end1] = -2
	dq = deque([(end1, 0)])
	while dq:
		(end2, diameter) = dq.popleft()
		for dest in adj[end2]:
			if prev[dest] == -1:
				prev[dest] = end2
				dq.append((dest, diameter + 1))
	return (end1, end2, diameter, prev)

def get_dist(st, dist):
	dist[st] = 0
	stack = [st]
	while stack:
		v = stack.pop()
		for dest in adj[v]:
			if dist[dest] != -1:
				continue
			dist[dest] = dist[v] + 1
			stack.append(dest)
(end1, end2, _, prev) = get_dia(adj)
dia_path = [0] * n
x = end2
while x != end1:
	dia_path[x] = 1
	x = prev[x]
dia_path[x] = 1
(dist1, dist2) = ([-1] * n, [-1] * n)
get_dist(end1, dist1)
get_dist(end2, dist2)
ans = []
score = 0
stack = [i for i in range(n) if deg[i] == 1 and dia_path[i] == 0]
while stack:
	v = stack.pop()
	deg[v] = 0
	if dist1[v] > dist2[v]:
		score += dist1[v]
		ans.append(f'{end1 + 1} {v + 1} {v + 1}')
	else:
		score += dist2[v]
		ans.append(f'{end2 + 1} {v + 1} {v + 1}')
	for dest in adj[v]:
		if dia_path[dest] == 0 and deg[dest] > 0:
			deg[dest] -= 1
			if deg[dest] <= 1:
				stack.append(dest)
x = end2
while x != end1:
	score += dist1[x]
	ans.append(f'{end1 + 1} {x + 1} {x + 1}')
	x = prev[x]
sys.stdout.buffer.write((str(score) + '\n' + '\n'.join(ans)).encode('utf-8'))


import sys

def main():
	n = int(input())
	edges = list(map(int, sys.stdin.read().split()))
	tree_edges = dict()
	for i in range(n):
		tree_edges[i + 1] = set()
	for i in range(0, len(edges) - 1, 2):
		tree_edges[edges[i]].add(edges[i + 1])
		tree_edges[edges[i + 1]].add(edges[i])
	init_distants = [-1] * (n + 1)
	queue = [1]
	init_distants[1] = 0
	while queue:
		next_queue = []
		for process in queue:
			for next_vertex in tree_edges[process]:
				if init_distants[next_vertex] == -1:
					init_distants[next_vertex] = init_distants[process] + 1
					next_queue.append(next_vertex)
		queue = next_queue
	head = init_distants.index(max(init_distants))
	distants_from_head = [-1] * (n + 1)
	queue = [head]
	distants_from_head[head] = 0
	while queue:
		next_queue = []
		for process in queue:
			for next_vertex in tree_edges[process]:
				if distants_from_head[next_vertex] == -1:
					distants_from_head[next_vertex] = distants_from_head[process] + 1
					next_queue.append(next_vertex)
		queue = next_queue
	tail = distants_from_head.index(max(distants_from_head))
	distants_from_tail = [-1] * (n + 1)
	queue = [tail]
	distants_from_tail[tail] = 0
	while queue:
		next_queue = []
		for process in queue:
			for next_vertex in tree_edges[process]:
				if distants_from_tail[next_vertex] == -1:
					distants_from_tail[next_vertex] = distants_from_tail[process] + 1
					next_queue.append(next_vertex)
		queue = next_queue
	path_len_sum = 0
	removal_history = list()
	process_queue = []
	for (vertex, adj) in list(tree_edges.items()):
		if len(adj) == 1:
			process_queue.append(vertex)
	while process_queue:
		next_queue = []
		for leaf in process_queue:
			if leaf == head or leaf == tail:
				continue
			if distants_from_tail[leaf] > distants_from_head[leaf]:
				path_len_sum += distants_from_tail[leaf]
				new_leaves = []
				for w in tree_edges[leaf]:
					tree_edges[w].remove(leaf)
					if len(tree_edges[w]) == 1:
						new_leaves.append(w)
				next_queue.extend(new_leaves)
				removal_history.append('{0} {1} {0}'.format(leaf, tail))
			else:
				path_len_sum += distants_from_head[leaf]
				new_leaves = []
				for w in tree_edges[leaf]:
					tree_edges[w].remove(leaf)
					if len(tree_edges[w]) == 1:
						new_leaves.append(w)
				next_queue.extend(new_leaves)
				removal_history.append('{0} {1} {0}'.format(leaf, head))
		process_queue = next_queue
	process_queue = [tail]
	while process_queue:
		leaf = process_queue[0]
		if leaf == head:
			continue
		path_len_sum += distants_from_head[leaf]
		new_leaves = []
		for w in tree_edges[leaf]:
			tree_edges[w].remove(leaf)
			if len(tree_edges[w]) == 1:
				new_leaves.append(w)
		process_queue = new_leaves
		removal_history.append('{0} {1} {0}'.format(leaf, head))
	print(str(path_len_sum))
	sys.stdout.write('\n'.join(removal_history))
	sys.stdout.write('\n')
main()


import sys
from collections import deque as dq
n = int(input())
ind = 0
inp = [int(x) - 1 for line in sys.stdin.readlines() for x in line.split()]
coupl = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = (inp[ind], inp[ind + 1])
	ind += 2
	coupl[a].append(b)
	coupl[b].append(a)
Q = dq()
found = [False] * n
master = 0
found[master] = True
dia1 = 0
Q.append(master)
while Q:
	node = Q.popleft()
	dia1 = node
	for nei in coupl[node]:
		if not found[nei]:
			found[nei] = True
			Q.append(nei)
dia2 = 0
Q.append((dia1, 0))
dist1 = [0] * n
found = [False] * n
found[dia1] = True
while Q:
	(node, d) = Q.popleft()
	dia2 = node
	dist1[node] = d
	for nei in coupl[node]:
		if not found[nei]:
			found[nei] = True
			Q.append((nei, d + 1))
Q = []
Q.append((dia2, 0))
dist2 = [0] * n
found = [False] * n
found[dia2] = True
while Q:
	(node, d) = Q.pop()
	dist2[node] = d
	for nei in coupl[node]:
		if not found[nei]:
			found[nei] = True
			Q.append((nei, d + 1))
neigs = [0] * n
leaves = []
for i in range(n):
	if i != dia1 and i != dia2 and (len(coupl[i]) == 1):
		leaves.append(i)
	neigs[i] = len(coupl[i])
points = 0
lista = []
while leaves:
	node = leaves.pop()
	if dist1[node] < dist2[node]:
		lista.append((dia2, node, node))
		points += dist2[node]
	else:
		lista.append((dia1, node, node))
		points += dist1[node]
	for nei in coupl[node]:
		neigs[nei] -= 1
		if neigs[nei] == 1:
			leaves.append(nei)
leaves.append(dia2)
while leaves:
	node = leaves.pop()
	lista.append((dia1, node, node))
	points += dist1[node]
	for nei in coupl[node]:
		neigs[nei] -= 1
		if neigs[nei] == 1:
			leaves.append(nei)
print(points)
for l in lista:
	(a, b, c) = l
	print(a + 1, b + 1, c + 1)


import sys
n = int(sys.stdin.buffer.readline().decode('utf-8'))
adj = [[] for _ in range(n)]
deg = [0] * n
for (u, v) in (map(int, line.decode('utf-8').split()) for line in sys.stdin.buffer):
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
	deg[u - 1] += 1
	deg[v - 1] += 1

def get_dia(st):
	stack = [(st, 0)]
	prev = [-1] * n
	prev[st] = -2
	(dia, t) = (0, -1)
	while stack:
		(v, steps) = stack.pop()
		if dia < steps:
			(dia, t) = (steps, v)
		for dest in adj[v]:
			if prev[dest] != -1:
				continue
			prev[dest] = v
			stack.append((dest, steps + 1))
	return (t, prev)

def get_dist(st, dist):
	dist[st] = 0
	stack = [st]
	while stack:
		v = stack.pop()
		for dest in adj[v]:
			if dist[dest] != -1:
				continue
			dist[dest] = dist[v] + 1
			stack.append(dest)
(edge1, _) = get_dia(0)
(edge2, prev) = get_dia(edge1)
dia_path = [0] * n
x = edge2
while x != edge1:
	dia_path[x] = 1
	x = prev[x]
dia_path[x] = 1
(dist1, dist2) = ([-1] * n, [-1] * n)
get_dist(edge1, dist1)
get_dist(edge2, dist2)
ans = []
score = 0
stack = [i for i in range(n) if deg[i] == 1 and dia_path[i] == 0]
while stack:
	v = stack.pop()
	deg[v] = 0
	if dist1[v] > dist2[v]:
		score += dist1[v]
		ans.append(f'{edge1 + 1} {v + 1} {v + 1}')
	else:
		score += dist2[v]
		ans.append(f'{edge2 + 1} {v + 1} {v + 1}')
	for dest in adj[v]:
		if dia_path[dest] == 0 and deg[dest] > 0:
			deg[dest] -= 1
			if deg[dest] <= 1:
				stack.append(dest)
x = edge2
while x != edge1:
	score += dist1[x]
	ans.append(f'{edge1 + 1} {x + 1} {x + 1}')
	x = prev[x]
sys.stdout.buffer.write((str(score) + '\n' + '\n'.join(ans)).encode('utf-8'))


import sys
input = sys.stdin.buffer.readline
n = int(input())
adj = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
dist1 = [0] * (n + 1)
dist2 = [0] * (n + 1)
diameter = []
on_diameter = [0] * (n + 1)
s = [1]
path = []
vis = [0] * (n + 1)
while s:
	c = s[-1]
	if not vis[c]:
		vis[c] = 1
		path.append(c)
		dist1[c] = len(path) - 1
		for ne in adj[c]:
			if not vis[ne]:
				s.append(ne)
	else:
		path.pop()
		s.pop()
mx_dist = 0
endpoint1 = 0
for i in range(1, n + 1):
	if dist1[i] > mx_dist:
		mx_dist = dist1[i]
		endpoint1 = i
s = [endpoint1]
path = []
vis = [0] * (n + 1)
while s:
	c = s[-1]
	if not vis[c]:
		vis[c] = 1
		path.append(c)
		dist1[c] = len(path) - 1
		for ne in adj[c]:
			if not vis[ne]:
				s.append(ne)
	else:
		path.pop()
		s.pop()
mx_dist = 0
endpoint2 = 0
for i in range(1, n + 1):
	if dist1[i] > mx_dist:
		mx_dist = dist1[i]
		endpoint2 = i
s = [endpoint2]
path = []
vis = [0] * (n + 1)
while s:
	c = s[-1]
	if not vis[c]:
		vis[c] = 1
		path.append(c)
		if c == endpoint1:
			diameter = path.copy()
		dist2[c] = len(path) - 1
		for ne in adj[c]:
			if not vis[ne]:
				s.append(ne)
	else:
		path.pop()
		s.pop()
for i in diameter:
	on_diameter[i] = 1
mx_answer = 0
operations = []
leaves = []
for i in range(1, n + 1):
	if len(adj[i]) == 1 and (not on_diameter[i]):
		leaves.append(i)
degree = [len(adj[i]) for i in range(n + 1)]
while leaves:
	c = leaves.pop()
	if dist1[c] > dist2[c]:
		mx_answer += dist1[c]
		operations.append([endpoint1, c, c])
	else:
		mx_answer += dist2[c]
		operations.append([endpoint2, c, c])
	for ne in adj[c]:
		degree[ne] -= 1
		if degree[ne] == 1:
			leaves.append(ne)
while len(diameter) > 1:
	c = diameter.pop()
	mx_answer += dist2[c]
	operations.append([endpoint2, c, c])
print(mx_answer)
for operation in operations:
	print(*operation)