样例数据过于水，因此提供一组数据。

Input

10
3 -1 -2 2 6 3 2 -5 7 1
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
6 10
7
1 8 5
1 9 10
2 1 3 0
1 2 7
1 9 10
2 2 5 2
1 8 5

Output

7 13 2 12 6

update:已添加一组数据，见本页底。

Sky1231 (sky1231) LV 10 @ 2020-10-23 09:50:39

我想說的是，你的2組數據都有一個特殊性：都容忍這種錯誤：即使用深度計算區間長度時，容忍把深度優先搜索順序當成節點編號，所以是很巧合的數據（事實上若犯上述錯誤，提交後任何一個測試點都不能通過，即vijos數據正式測評為0分）。
例子：https://vijos.org/discuss/5f904ca0f413624954eb889d#1603416980
Bill_Yang LV 10 @ 2017-08-04 22:32:20
然而我发现这仍然不典型，再添加一组

Input
```
10
3 -1 -2 2 6 3 2 -5 7 1
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
6 10
5
1 8 5
1 9 10
2 2 6 0
1 4 5
1 10 7
```
Output
```
7 13 8 3
```
如果输出
```
7 13 7 3
```
就想想为什么吧