← 返回题目列表

Codeforces · 767/C

C. 花环

中文机器翻译题面 查看原题

有一次新年时,迪马做了一个梦,梦中有人向他赠送了一个仙女花环。花环是一组灯,其中一些灯对通过电线连接。迪玛记得花环里的每两盏灯都是通过一些电线直接或间接连接的。而且,电线的数量比灯的数量正好少一根。

这个花环有些不寻常。每个灯都有自己的亮度,亮度取决于灯的温度。温度可以是正值、负值或零。迪马有两个朋友,所以他决定与他们分享花环。他想剪断两根不同的电线,使花环分成三部分。花环的每个部分都应该同样闪亮,即。 e.每个部分的灯温度总和应相等。当然,每个部分都应该是非空的,即。 e.每个部分应至少包含一盏灯。

帮助迪玛找到合适的方法来切割花环,或者确定这是不可能的。

在检查花环时,迪玛拿着一盏灯将其举起。因此,除了他拿着的那盏灯外,每一盏灯现在都挂在一根电线上。因此,您应该打印两个灯 id 作为答案,这表示 Dima 应该切断这些灯所悬挂的电线。当然,迪玛拿着花环的灯不能包含在答案中。

输入

第一行包含单个整数 n (3 ≤ n ≤ 106) — 花环中灯的数量。

接下来是 n 行。其中第 i 个包含有关第 i 个灯的信息:悬挂的灯号 ai(如果没有这样的灯,则为 0)及其温度 ti (- 100 ≤ ti ≤ 100)。灯的编号为 1 到 n。

输出

如果没有解,则打印-1。

否则打印两个整数——灯的索引,这意味着 Dima 应该切断它们悬挂的电线。如果有多个答案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

1 4

输入 #2

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

输出 #2

-1

注意

第一个示例的花环和切割方案: