Готуй адвокатів
Limits: 2 sec., 256 MiB
Зеник живе в країні з дуже цікавою історією. Ця країна існує вже \(h\) років. У перший рік існування в ній було побудовано лише одне місто — столицю. Кожен наступний рік для кожного міста, побудованого у попередньому році, було побудовано по два додаткові міста, які були з’єднані з ним двосторонніми дорогами. Отже, після \(h\) років у країні було рівно \(2^h-1\) міст та \(2^h-2\) доріг.
Недавно якесь бісеня «для покращення інфраструктури країни» добудувало рівно три дороги між певними парами міст. Цим самим, на думку Зеника, вся краса країни була втрачена, і він вирішив подати на цю особу позов до суду.
У Зеника є список усіх доріг країни, проте він не знає, коли яка дорога була додана, та яким чином пронумеровані міста. Для того, щоб підготувати позов, йому потрібно знати, які три із цих доріг могли бути доданими останніми. Допоможіть йому знайти їх.
Input
У першому рядку задано одне ціле число \(h\) — кількість років, протягом яких батьківщина Зеника існує.
У наступних \(2^h+1\) рядках задано пари цілих чисел, по одній парі на рядок. Кожна з цих пар позначає номера міст, з’єднаних відповідною дорогою.
Міста пронумеровані цілими числами від 1 до \(2^h-1\) включно.
Дороги пронумеровані цілими числами від 1 до \(2^h+1\) включно, в порядку із вхідних даних.
Output
У єдиному рядку виведіть три різних цілих числа через пробіл — номери доріг, які могли бути доданими останніми.
Якщо існує декілька варіантів відповіді, спочатку мінімізуйте перше число, після цього мінімізуйте друге, потім — третє.
Якщо не існує відповіді, тобто список доріг є некоректним, виведіть
-1
.
Constraints
\(2 \le h \le 10\).
Samples
Input (stdin) | Output (stdout) |
---|---|
3 1 6 3 5 2 4 2 7 3 4 7 3 1 3 5 1 4 7 | 2 3 5 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|