Generous sponsors of the olympiad in which Chloe and Vladik took part allowed all the participants to choose a prize for them on their own. Christmas is coming, so sponsors decided to decorate the Christmas tree with their prizes. 

They took n prizes for the contestants and wrote on each of them a unique id (integer from 1 to n). A gift i is characterized by integer a_{i} — pleasantness of the gift. The pleasantness of the gift can be positive, negative or zero. Sponsors placed the gift 1 on the top of the tree. All the other gifts hung on a rope tied to some other gift so that each gift hung on the first gift, possibly with a sequence of ropes and another gifts. Formally, the gifts formed a rooted tree with n vertices.

The prize-giving procedure goes in the following way: the participants come to the tree one after another, choose any of the remaining gifts and cut the rope this prize hang on. Note that all the ropes which were used to hang other prizes on the chosen one are not cut. So the contestant gets the chosen gift as well as the all the gifts that hang on it, possibly with a sequence of ropes and another gifts.

Our friends, Chloe and Vladik, shared the first place on the olympiad and they will choose prizes at the same time! To keep themselves from fighting, they decided to choose two different gifts so that the sets of the gifts that hang on them with a sequence of ropes and another gifts don't intersect. In other words, there shouldn't be any gift that hang both on the gift chosen by Chloe and on the gift chosen by Vladik. From all of the possible variants they will choose such pair of prizes that the sum of pleasantness of all the gifts that they will take after cutting the ropes is as large as possible.

Print the maximum sum of pleasantness that Vladik and Chloe can get. If it is impossible for them to choose the gifts without fighting, print Impossible.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 2·10^5) — the number of gifts.

The next line contains n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the pleasantness of the gifts.

The next (n - 1) lines contain two numbers each. The i-th of these lines contains integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the description of the tree's edges. It means that gifts with numbers u_{i} and v_{i} are connected to each other with a rope. The gifts' ids in the description of the ropes can be given in arbirtary order: v_{i} hangs on u_{i} or u_{i} hangs on v_{i}. 

It is guaranteed that all the gifts hang on the first gift, possibly with a sequence of ropes and another gifts.


-----Output-----

If it is possible for Chloe and Vladik to choose prizes without fighting, print single integer — the maximum possible sum of pleasantness they can get together.

Otherwise print Impossible.


-----Examples-----
Input
8
0 5 -1 4 3 2 6 5
1 2
2 4
2 5
1 3
3 6
6 7
6 8

Output
25
Input
4
1 -5 1 1
1 2
1 4
2 3

Output
2
Input
1
-1

Output
Impossible

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Graph algorithms

Graph traversal

Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
input = sys.stdin.readline
oo = 10 ** 20
n = int(input())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = [int(i) - 1 for i in input().split()]
	adj[u].append(v)
	adj[v].append(u)
sm = [0] * n
mx = [-oo] * n
best = [-oo] * n
stack = [(0, -1)]
visit = [False] * n
while stack:
	(u, p) = stack[-1]
	if not visit[u]:
		for v in adj[u]:
			if v != p:
				stack.append((v, u))
		visit[u] = True
	else:
		x = [-oo] * 3
		for v in adj[u]:
			if v != p:
				sm[u] += sm[v]
				mx[u] = max(mx[u], mx[v])
				best[u] = max(best[u], best[v])
				x[0] = mx[v]
				x.sort()
		sm[u] += a[u]
		mx[u] = max(mx[u], sm[u])
		if x[1] > -oo and x[2] > -oo:
			cur = x[1] + x[2]
			best[u] = max(best[u], cur)
		stack.pop()
ans = max(best)
if ans <= -oo:
	print('Impossible')
else:
	print(ans)


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(2 * 10 ** 5)

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(u, p):
	for j in adj[u]:
		if j != p:
			yield dfs(j, u)
			f[u] += f[j]
			res[u] = max(res[u], res[j])
	f[u] += b[u - 1]
	res[u] = max(res[u], f[u])
	yield

@bootstrap
def dfs2(u, p, val):
	global ans
	if val != -float('inf'):
		ans = max(ans, f[u] + val)
	req = []
	for j in adj[u]:
		if j != p:
			req.append([res[j], j])
	req.sort(reverse=True)
	req.append([-float('inf'), -1])
	for j in adj[u]:
		if j != p:
			if req[0][1] == j:
				yield dfs2(j, u, max(val, req[1][0]))
			else:
				dfs2(j, u, max(val, req[0][0]))
	yield
n = int(input())
b = list(map(int, input().split()))
adj = [[] for i in range(n + 1)]
for j in range(n - 1):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
f = [0] * (n + 1)
res = [-float('inf')] * (n + 1)
dfs(1, 0)
ans = -float('inf')
dfs2(1, 0, -float('inf'))
if ans == -float('inf'):
	print('Impossible')
else:
	print(ans)


import sys
import threading
from math import *

def ri():
	return map(int, sys.stdin.readline().split())

def dfsv(u):
	global ans
	h1 = -inf
	h2 = -inf
	for i in adj[u]:
		if v[i] == 0:
			v[i] = 1
			dfsv(i)
			s[u] += s[i]
			if h1 < h[i]:
				h2 = h1
				h1 = h[i]
			elif h2 < h[i]:
				h2 = h[i]
	ans = max(ans, h1 + h2)
	h[u] = max(h1, s[u])
	return
n = int(input())
a = list(ri())
adj = [[] for i in range(n)]
v = [0 for i in range(n)]
s = [a[i] for i in range(n)]
h = [0 for i in range(n)]
for i in range(n - 1):
	(aa, bb) = ri()
	aa -= 1
	bb -= 1
	adj[aa].append(bb)
	adj[bb].append(aa)
ans = -inf

def solve():
	v[0] = 1
	dfsv(0)
	if ans == -inf:
		print('Impossible')
	else:
		print(ans)
max_recur_size = 10 ** 5 * 2 + 1000
max_stack_size = max_recur_size * 500
sys.setrecursionlimit(max_recur_size)
threading.stack_size(max_stack_size)
thread = threading.Thread(target=solve)
thread.start()


import sys
from math import inf
import threading

def dfs(g, i, v, n, p):
	global exist, ans
	summ = v[i - 1]
	first = -inf
	second = -inf
	maxm = -inf
	for j in g[i]:
		if j == p:
			continue
		(sum_child, max_child) = dfs(g, j, v, n, i)
		summ += sum_child
		if max_child >= first:
			second = first
			first = max_child
		elif max_child > second:
			second = max_child
	ans = max(ans, first + second)
	maxm = max(first, summ)
	return (summ, maxm)

def solve():
	n = int(input())
	v = list(map(int, sys.stdin.readline().split()))
	g = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		g[x].append(y)
		g[y].append(x)
	(_, a) = dfs(g, 1, v, n, 0)
	if not ans == -inf:
		print(ans)
	else:
		print('Impossible')
ans = -inf
max_recur_size = 10 ** 5 * 2 + 1000
max_stack_size = max_recur_size * 500
sys.setrecursionlimit(max_recur_size)
threading.stack_size(max_stack_size)
thread = threading.Thread(target=solve)
thread.start()