Боб в країні чудес

Ланцюг, як відомо, складається із зв'язаних ланок. Зазвичай усі ланки мають однакову форму та розмір. Боб - учень коваля, і він робить свій перший іридієвий ланцюжок. Він слідує традиційній формулі створення ланцюгів. Вона каже:

• Якщо ланцюжка ще немає, зробіть ланку, і вона стане частиною вашого ланцюжка.

• Якщо вже є шматок ланцюга, зробіть ще одну ланку і з'єднайте її з іншою ланкою в ланцюзі.

Боб зробив першу ланку. Потім, кожного разу, коли він створював нову ланку, він з'єднував її з якоюсь іншою ланкою ланцюга, точно так, як йому каже формула.

Коли він закінчив, то зрозумів, що створений ним об'єкт зовсім не схожий на звичайний ланцюжок. Намагаючись випрямити ланцюг, він кілька разів брав дві ланки, які, здавалося, знаходилися на кінцях ланцюга, і намагався розвести їх якнайдалі. Але було ще кілька частин «ланцюжка», що звисають із випрямленої частини у різних місцях.

Для Боба було очевидно, що його роботу ще не закінчено, і він вирішив назвати створений ним об'єкт незавершеним ланцюжком. Подумавши ще трохи, Боб дійшов висновку, що він повинен розірвати деякі ланки і акуратно з'єднати їх з рештою незавершеного ланцюга, щоб отримати прямий ланцюг, який він має намір зробити. У прямому ланцюзі кожна ланка з'єднана не більше ніж з двома іншими ланками. Прямий ланцюг не може бути розділений на кілька частин без розриву ланки.

Будучи тепер обережнішим, Боб просуватиметься вперед простими кроками. На одному кроці він вибере ланку $A$, пов'язану з іншою ланкою $B$, у незавершеному ланцюжку. Потім він зламає $A$, від'єднає його від $B$ і повторно під'єднає $A$ до будь-якої іншої ланки, наприклад $C$, у незавершеному ланцюжку. Якщо є ще ланки, крім $B$, спочатку підключені до $A$, Боб буде підтримувати їх підключеними до $A$ протягом усього кроку.

Яку мінімальну кількість кроків має виконати Боб, щоб отримати прямий ланцюжок?

Вихідні дані

Виведіть мінімальну кількість кроків, які перетворять незакінчений ланцюжок Боба на прямий.