C. Garland time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Once at New Year Dima had a dream in which he was PResented a fairy garland. A garland is a set of lamps, some pairs of which are connected by wires. Dima remembered that each two lamps in the garland were connected directly or indirectly via some wires. Furthermore, the number of wires was exactly one less than the number of lamps.

There was something unusual about the garland. Each lamp had its own brightness which depended on the temperature of the lamp. Temperatures could be positive, negative or zero. Dima has two friends, so he decided to share the garland with them. He wants to cut two different wires so that the garland breaks up into three parts. Each part of the garland should shine equally, i. e. the sums of lamps’ temperatures should be equal in each of the parts. Of course, each of the parts should be non-empty, i. e. each part should contain at least one lamp.

Help Dima to find a suitable way to cut the garland, or determine that this is impossible.

While examining the garland, Dima lifted it up holding by one of the lamps. Thus, each of the lamps, except the one he is holding by, is now hanging on some wire. So, you should print two lamp ids as the answer which denote that Dima should cut the wires these lamps are hanging on. Of course, the lamp Dima is holding the garland by can’t be included in the answer.

Input The first line contains single integer n (3?≤?n?≤?106) — the number of lamps in the garland.

Then n lines follow. The i-th of them contain the information about the i-th lamp: the number lamp ai, it is hanging on (and 0, if is there is no such lamp), and its temperature ti (?-?100?≤?ti?≤?100). The lamps are numbered from 1 to n.

Output If there is no solution, print -1.

Otherwise print two integers — the indexes of the lamps which mean Dima should cut the wires they are hanging on. If there are multiple answers, print any of them.

Examples input 6 2 4 0 5 4 2 2 1 1 1 4 2 output 1 4 input 6 2 4 0 6 4 2 2 1 1 1 4 2 output -1 題意：給你一棵樹，樹上的每個節點有權值，權值有正有負還有0，問你能不能把這棵樹變成權值和相等的三部分 解題思路：我們知道要把一棵樹變成3部分，就必須刪除兩條邊，題目雖然沒有說這棵樹是有根樹，但是我們可以把它當成有根樹，令dp[i]為以i為根節點的子樹的權值和，然后dfs根，如果中間出現sum/3，就刪除該子樹。為什么這種做法是對的，我們來簡單的證明一下：假設最后是有解的，也就是可以把這棵樹分成三等份，所以最后這棵樹一定被刪除了兩條邊，我們把這棵樹看成有根樹（以哪個節點為根沒有關系，但是這里為了方便，取了一個特殊的點），也就是在這棵有根樹中需要刪除兩條邊，而在有根樹中刪除一條邊產生的效果就是產生一棵子樹，所以最后一定能得到解。需要注意的是這里刪除子樹的做法是讓dp[u] = 0就行，u 是子樹的根。