Задачі
Декартове дерево
Декартове дерево
Розглянемо один спеціальний тип двійкових дерев пошуку, який часто називають "декартовим деревом". Нагадаємо, що двійковим деревом пошуку називається двійкове дерево, у кожній вершині якого записано деякий ключ (у цій задачі ключ являє собою ціле число), причому для кожної вершини \textbf{u} виконані наступні умови: усі ключі у лівому піддереві \textbf{u} менші ніж ключ у вершині \textbf{u}, а усі ключі у правому піддереві --- більші.
Будемо називати двійкове дерево пошуку декартовим деревом, якщо у кожній вершині \textbf{u} крім основного ключа \textbf{x_u} зберігається також допоміжний ключ \textbf{y_u}, причому для цих ключів виконана "умова кучі": якщо \textbf{v} --- предок \textbf{u}, то \textbf{y_v} < \textbf{y_u}.
Будемо називати множину пар (\textbf{x_1}, \textbf{y_1}), (\textbf{x_2}, \textbf{y_2}), ..., (\textbf{x_n}, \textbf{y_n}) \textit{корректною}, якщо усі \textbf{x_i} --- різні числа від \textbf{1} до \textbf{n}, і ця ж умова виконана для \textbf{y_i}. Легко показати, що для довільної коректної множини пар існує у точності одне декартове дерево, яке містить пари з заданої множини у якості пар ключів.
Розглянемо двійкове дерево \textbf{T} з \textbf{n} вершинами. Ваша задача --- знайти кількість різних коректних множин пар, таких що їх можна розставити у вершинах \textbf{T}, щоб перетворити його у декартове дерево.
Наприклад, для дерева, наведеного на рисунку, існує три відповідних коректних множини пар:
\textbf{\{(1},\textbf{ 2)},\textbf{ (2},\textbf{ 3)},\textbf{ (3},\textbf{ 1)},\textbf{ (4},\textbf{ 4)\}}, \textbf{\{(1},\textbf{ 2)},\textbf{ (2},\textbf{ 4)},\textbf{ (3},\textbf{ 1)},\textbf{ (4},\textbf{ 3)\}} и \textbf{\{(1},\textbf{ 3)},\textbf{ (2},\textbf{ 4)},\textbf{ (3},\textbf{ 1)},\textbf{ (4},\textbf{ 2)\}}.
\includegraphics{https://static.e-olymp.com/content/00/00abd9c2467bf626ac2c64a19ffd566b56c6887b.jpg}
\InputFile
Перший рядок вхідного файлу містить \textbf{n} --- кількість вершин у дереві \textbf{T} (\textbf{1} ≤ \textbf{n} ≤ \textbf{200}). Наступні \textbf{n} рядків описують його вершини. Кожна вершина описується двома числами: номерами лівої та правої дитини. Якщо одне з дітей відсутнє, то замість його номера вказано \textbf{0}. Гарантується, що опис дерева коректний. Корінь дерева має номер \textbf{1}.
\OutputFile
Виведіть одне число --- кількість різних коректних множин пар, які можна розставити у вершинах \textbf{T}, щоб отримати декартове дерево.
Вхідні дані #1
4 2 3 0 4 0 0 0 0
Вихідні дані #1
3