Codeforces Round 398 (Div. 2) |
---|
Закончено |
Однажды под Новый Год Диме приснилось, что ему подарили сказочную гирлянду. Гирлянда — это набор лампочек, некоторые пары которых соединены проводами. Дима запомнил, что она представляла из себя единое целое, то есть любая пара лампочек была связана некоторой последовательностью проводов. Еще он заметил, что проводов было ровно на один меньше, чем лампочек.
Необычность гирлянды состояла в том, что яркость каждой лампочки зависела от температуры этой лампочки, которая могла быть как отрицательной, так и положительной! У Димы есть два друга, и он захотел поделиться с ними сказочным подарком. Для этого он планирует разрезать два разных провода так, чтобы гирлянда распалась на три части. Дима хочет, чтобы все три части светились одинаково, то есть чтобы в каждой из них суммарная температура лампочек совпадала. Конечно же, каждая из частей должна быть непустой, то есть в ней должна быть хотя бы одна лампочка.
Помогите ему найти способ, как это сделать, либо определите, что такого не существует.
Осматривая гирлянду, Дима поднял ее, взяв за какую-то лампочку. Таким образом, каждая лампочка, кроме той, за которую он взял, оказалась висящей на некотором проводе. Поэтому в качестве ответа вам нужно вывести номера двух различных лампочек, что будет означать, что Диме нужно разрезать провода, за которые они подвешены. Соответственно, в ответ не может входить лампочка, за которую Дима взял гирлянду.
В первой строке находится целое число n (3 ≤ n ≤ 106) — количество лампочек в гирлянде.
Затем следует n строк: в i-й из них находится информация об i-й лампочке, а именно, два целых числа — номер лампочки ai, к которой она подвешена (если такой нет, то число 0), и температура ti ( - 100 ≤ ti ≤ 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
Схема гирлянды и разрезаний к первому примеру из условия:
Название |
---|