该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

探险队获得了一张藏宝图，藏宝图中有 $n$ 个洞穴，还有 $n-1$ 条道路连通这 $n$ 个洞穴，对于任意两个不同的洞穴，都可以通过道路相互到达。

在藏宝图中，一些洞穴里被标记有宝藏。

探险队决定选取一些有宝物的洞穴作为寻宝计划，他们会从寻宝计划中的一个洞穴出发，依次到达每个寻宝计划中其他的洞穴收集宝物，最后再回到出发的洞穴，在这个过程中，他们会选择路程最少的寻宝路线。可以证明，无论从寻宝计划中的哪个洞穴出发，最终的最小路程都是相同的。

一次探险的路程是探险中经过的道路数量。

现在你需要计算对于每个 $k(1 \leq k \leq n)$，在探险队任选 $k$ 个有宝物的洞穴作为寻宝计划时，他们要走的最小路程最多是多少，最少是多少？

输入格式

第一行输入一个正整数 $n(1 \leq n \leq 3000)$，代表洞穴的个数。

第二行输入 $n$ 个整数 $a_i (0 \leq a_i \leq 1)$，若 $a_i = 1$ 则表示第 $i$ 个洞穴中有宝物，否则代表这个洞穴没有宝物。

接下来 $n-1$ 行，每行读入两个正整数 $x,y(1 \leq x,y \leq n)$ 代表一条连接洞穴的道路。

输出格式

输出 $n$ 行，每行两个正整数，第 $i$ 行代表在选择 $i$ 个宝物的前提下，最小路程最多的选择方案和最小路程最少的选择方案对应的路程，若地图中不足 $i$ 个宝物，则输出 -1 -1。

5
1 0 0 1 1
1 2
2 3
3 4
3 5

0 0
6 4
8 8
-1 -1
-1 -1

解释 #1

在 $k=2$ 时，路程最多的方案是选择 $\{1,4\}$ 或者 $\{1,5\}$，路程最少的方案是选择 $\{4,5\}$。