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.

The first line contains single integer n (3?≤?n?≤?10⁶) — 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 a_i, it is hanging on (and0, if is there is no such lamp), and its temperaturet_i (?-?100?≤?t_i?≤?100). The lamps are numbered from1 to n.

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.

62 40 54 22 11 14 2Output
1 4Input
62 40 64 22 11 14 2Output
-1Note
The garland and cuts scheme for the first example:
解題思路:
統計每棵子樹的加和,然后dfs每個節點,查看這些子樹是否所有節點總和sum/3的倍數為什么是倍數而不是sum/3呢,因為有可能出現一個節點所在子樹的和是sum/3,而它父親節點只有這一個兒子,且這個父親節點的權值是sum/3,也就是說父親節點所在子樹的和是2*sum/3,這樣的情況明顯是可以分割的,如果我們只是檢查是否是sum/3,這種情況可能就漏掉了.
代碼:
#include <bits/stdc++.h>using namespace std;const int maxn=1e6+5;int temp[maxn];int a[maxn];vector<int> edg[maxn];int vis[maxn];int an[11];int top;int xx;int k;int dfs2(int a, int b){    int tt=0;    for(int i=0; i<(int) edg[a].size(); i++)    {	if(edg[a][i]!=b)	{		tt+=dfs2(edg[a][i], a);		temp[a]+=temp[edg[a][i]];	}    }    if(k)    {       if(temp[a]== (tt+1)*k)vis[a]=++tt;    }    return tt;}int main(){   int n;   cin>>n;   int i;   int root;   top=0;   int sum=0;   for(i=1; i<=n; i++)   {      scanf("%d %d", &a[i], &temp[i]);      sum+=temp[i];      if(a[i]==0)root=i;      edg[a[i]].push_back(i);      edg[i].push_back(a[i]);   }  /* for(i=1; i<=n; i++)   {	for(int j=0; j<(int)edg[i].size(); j++)	{	    printf("%d ", edg[i][j]);	}	printf("/n");   }*/   xx=0;  // printf("%d/n", root);   edg[0].push_back(0);   if(sum%3!=0)   {     return 0*printf("-1/n");   }   k=sum/3;   int ans=dfs2(root, 0);   if(ans<3)return 0*printf("-1/n"); //  printf("%d/n", sum);   int j=2;   for(i=1; i<=n; i++)   {     if(vis[i]==1 || vis[i]==2){printf("%d", i);j--;     if(j)printf(" ");     else break;     }   }}