题目描述

新年那天，小明做了一个梦，梦见有人送给他一串仙女花环。花环是一组灯泡，其中一些灯泡通过电线连接在一起。小明记得花环中的每两个灯泡都通过电线直接或间接地连接在一起。此外，电线的数量恰好比灯泡的数量少一个。（也就是说，这些灯泡和电线的整体是一个树形结构）

花环有一些不寻常之处。每个灯泡都有自己的亮度，这取决于灯泡的温度。温度可以是正数、负数或零。小明有两个朋友，所以他决定与他们分享这个花环。他想要剪断两根不同的电线，使花环分成三部分。花环的每一部分都应该同样发光，即每一部分中灯泡的温度之和应该相等。当然，每一部分都不应为空，即每一部分都应该至少包含一个灯泡。

帮助小明找到合适的方法来剪断花环，或者确定这是不可能的。

在检查花环时，小明把它举起，只用一盏灯来支撑。因此，除了他用来支撑的那盏灯之外，每盏灯现在都悬挂在某根电线上。所以你的输出应该是两个整数，这两个整数对应两个灯泡的编号，你应该删除的就是这两个灯泡所悬挂在的绳子。当然，小明用来支撑花环的那盏灯不能包含在答案中。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 10^6$) —— 花环中的灯的数量。

接下来有 $n$ 行。第 $i$ 行包含了关于第 $i$ 盏灯的信息：灯的编号 $a_i$，表示它所悬挂在的灯（即它挂在哪盏灯下面，如果没有这样的灯，即第 $i$ 盏灯是用于支撑的那盏灯，则 $a_i = 0$），以及它的温度 $t_i$ ($-100 \le t_i \le 100$)。灯的编号从 $1$ 到 $n$。

输出格式

如果没有解决方案，输出 $-1$。

否则，打印两个整数，以一个空格分隔，表示小明应该剪断它们所悬挂的电线的编号。如果有多个答案，可以输出其中任意一个。

样例

6
2 4
0 5
4 2
2 1
1 1
4 2

1 4

6
2 4
0 6
4 2
2 1
1 1
4 2

-1

说明/提示

样例 1 解释

样例 1 中的花环和剪断方案如下：

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 100$
• 对于 $50\%$ 的数据，$n \le 10000$
• 对于 $100\%$ 的数据，$3 \le n \le 10^6, -100 \le t_i \le 100$