Декартове дерево
Розглянемо один спеціальний тип двійкових дерев пошуку, який часто називають "декартовим деревом". Нагадаємо, що двійковим деревом пошуку називається двійкове дерево, у кожній вершині якого записано деякий ключ (у цій задачі ключ являє собою ціле число), причому для кожної вершини u виконані наступні умови: усі ключі у лівому піддереві u менші ніж ключ у вершині u, а усі ключі у правому піддереві — більші.
Будемо називати двійкове дерево пошуку декартовим деревом, якщо у кожній вершині u крім основного ключа x_u зберігається також допоміжний ключ y_u, причому для цих ключів виконана "умова кучі": якщо v — предок u, то y_v < y_u.
Будемо називати множину пар (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) корректною, якщо усі x_i — різні числа від 1 до n, і ця ж умова виконана для y_i. Легко показати, що для довільної коректної множини пар існує у точності одне декартове дерево, яке містить пари з заданої множини у якості пар ключів.
Розглянемо двійкове дерево T з n вершинами. Ваша задача — знайти кількість різних коректних множин пар, таких що їх можна розставити у вершинах T, щоб перетворити його у декартове дерево.
Наприклад, для дерева, наведеного на рисунку, існує три відповідних коректних множини пар:
{(1, 2), (2, 3), (3, 1), (4, 4)}, {(1, 2), (2, 4), (3, 1), (4, 3)} и {(1, 3), (2, 4), (3, 1), (4, 2)}.
Вхідні дані
Перший рядок вхідного файлу містить n — кількість вершин у дереві T (1 ≤ n ≤ 200). Наступні n рядків описують його вершини. Кожна вершина описується двома числами: номерами лівої та правої дитини. Якщо одне з дітей відсутнє, то замість його номера вказано 0. Гарантується, що опис дерева коректний. Корінь дерева має номер 1.
Вихідні дані
Виведіть одне число — кількість різних коректних множин пар, які можна розставити у вершинах T, щоб отримати декартове дерево.