eolymp
bolt
Try our new interface for solving problems
Məsələlər

Это левая куча?

Это левая куча?

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Потенциалом вершины в подвешенном двоичном дереве назовём кратчайшее расстояние до вершины у которой меньше двух детей. Дерево называется левым, если левый сын каждой вершины имеет не меньший потенциал, чем правый. Так же не должно существовать вершины, у которой есть правый, но нет левого сына.

По заданному двоичному дереву найдите наименьшую вершину, для которой нарушается свойство.

Giriş verilənləri

В первой строке задано количество вершин дерева N (1N10^5). Последующие N строк описывают индексы левого и правого сына соответственно l_i, r_i (i < l_in, i < r_in). Если l_i или r_i равно -1 - это означает, что такого сына нет.

Çıxış verilənləri

Выведите наименьший номер вершины, для которой нарушено свойство, или -1, если такой вершины не существует.

Nümunə

Giriş verilənləri #1
3
2 3
-1 -1
-1 -1
Çıxış verilənləri #1
-1