CF767C Garland

新年时，Dima 做了一个梦，梦中他收到了一串神奇的彩灯。这串彩灯由若干个灯泡组成，其中一些灯泡两两之间由导线直接相连。Dima 记得，每两个灯泡都通过某些导线直接或间接地连通。此外，导线的数量恰好比灯泡的数量少 $1$。 这串彩灯有些特别：每个灯泡有自己的亮度，亮度取决于灯泡的温度。温度可以是正数、负数或零。Dima 有两个朋友，他决定把彩灯分成三份。Dima 想剪断两根不同的导线，使得整串彩灯断成三部分。每一部分的亮度之和（即灯泡温度之和）应当相等。同时，每一部分都不能为空，也就是说每部分至少包含一个灯泡。  请帮助 Dima 找到一种合适的剪断方案，或者判断不存在这样的方案。 在检查彩灯时，Dima 用手提着其中一个灯泡。所以，除他手持的灯泡外，其余灯泡都通过某根导线悬挂。你需要输出两个灯泡的编号，表示 Dima 应该剪断这两个灯泡所悬挂的导线。显然，Dima 手里拿着的灯泡不能包括在答案中。

第一行是一个整数 $n$（$3\le n\le 10^6$），表示彩灯中灯泡的数量。 接下来有 $n$ 行。第 $i$ 行包含两个整数，分别为 $a_i$ 和 $t_i$，表示第 $i$ 个灯泡悬挂在编号为 $a_i$ 的灯泡上（如果没有则为 $0$），以及第 $i$ 个灯泡的温度 $t_i$（$-100 \le t_i \le 100$）。灯泡的编号从 $1$ 到 $n$。

如果不存在可行方案，输出 $-1$。 否则，输出两个整数，表示应当剪断这两个灯泡悬挂的导线。若有多组答案，输出任意一组即可。

下图给出了第一个样例的彩灯和剪断位置的示意图：  由 ChatGPT 5 翻译