众所周知，Bajtazar 是一个非常忙碌的人，他不惧怕在 Bitocja 等待他的任何生活挑战。最终，他决定休息一下，去 Bitocja 度假。Bitocja 有 $n$ 个城市，由 $n - 1$ 条双向道路连接，使得任意两个城市之间都可以互相到达。Bajtazar 不想连续两天待在同一个城市，但他也不喜欢太长的行程，所以每天晚上他计划沿着一条道路移动到相邻的城市。对于每个城市，Bajtazar 都设定了一个吸引力系数，这决定了游览该城市对他来说有多愉快。当然，他希望度过一个尽可能愉快的假期。

Bajtazar 不会是他自己，如果他不把愉快与实用结合起来。因此，他将利用假期时间开始写日记。具体来说，他只会在假期的每隔一天进行游览，其余时间用于写作。

他想计划一个长度为 $2k - 1$ 天的假期，其中在 $k$ 个奇数天他会进行游览，而在 $k - 1$ 个偶数天他会写日记。游览城市的吸引力系数之和必须尽可能大，同时 Bajtazar 不想游览同一个城市超过一次。然而，他不介意在写日记的日子里，他会待在之前已经去过的城市。请帮他计划一个尽可能愉快的假期。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示 Bitocja 的城市数量。城市编号从 $1$ 到 $n$。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 1\,000\,000$)，用空格分隔；数字 $w_i$ 表示编号为 $i$ 的城市的吸引力系数。

接下来的 $n - 1$ 行描述了 Bitocja 的道路；第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$)，用空格分隔，表示连接编号为 $a_i$ 和 $b_i$ 的城市之间存在一条双向道路。

输出格式

你的程序应该输出三行。第一行应包含一个整数 $W$，表示 Bajtazar 假期可以获得的最大吸引力系数之和。

第二行应包含一个整数 $k$，表示 Bajtazar 在假期中将游览的城市数量。第三行应包含 $2k - 1$ 个用空格分隔的数字，表示 Bajtazar 在假期后续日子里所处的城市。如果存在多个最大值为 $W$ 的解，你的程序可以输出其中任意一个。

样例

样例输入 1

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

样例输出 1

13
4
3 2 1 2 4 6 7

说明

样例解释：图中展示了 Bitocja 的道路网络结构。Bajtazar 将游览编号为 3, 1, 4 和 7 的城市；这些城市的吸引力系数之和为 $5 + 3 + 4 + 1 = 13$。

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。

如果你的程序正确输出了输出的第一行（数字 $W$），而其余行不正确，则将获得该测试点分数的 40%。