Garland
Contest: Codeforces Round 398 (Div. 2)
Difficulty rating: 2000
Tags: dfs and similar, graphs, greedy, trees

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The garland and cuts scheme for the first example:

Example input:
6
2 4
0 5
4 2
2 1
1 1
4 2

Example output:
1 4

Example input:
6
2 4
0 6
4 2
2 1
1 1
4 2

Example output:
-1

Editorial:
We can note that the given graph is a tree. Let's perform a dfs from the root of the tree.
Let's calculate the sums if ti in each subtree, let this value be sv for the subtree of the vertex v. In order to compute sv we need to recursively call dfs from all sons of v and add the value tv.
Let the overall sum of ti be equal to x. If x is not divisible by three, there is no answer. Otherwise there are two different cases (let the answer lamps be v1 and v2) to obtain three subtrees with equal sum (x / 3):
1. One of the vertices is an ancestor of the other (we can think that v2 is ancestor of v1), then sv2 = 2x / 3, sv1 = x / 3.
2. Neither v1 nor v2 is ancestor of the other. In this case sv1 = sv2 = x / 3
To check the first option, it is enough to track is the dfs if there is at least one vertex u in the subtree of current vertex v with sum su = x / 3. If there is one, and sv = 2x / 3, then there is an answer v2 = v, v1 = u.
To check the second option, let's write down all vertices v such that sv = x / 3 and there isno other u with su = x / 3 in the subtree of v. Note that we do the same thing when checking the first option. So, if there are at least two vertices we wrote down, they form the answer we are looking for.