Jingle Balls
Незабаром настане час прикрашати різдвяну ялинку. Судді NWERC вже обговорюють оптимальний спосіб розміщення прикрас на дереві. Вони погоджуються, що важливо рівномірно розподілити прикраси по гілках дерева.
Ця задача обмежується бінарними різдвяними деревами. Такі дерева складаються зі стовбура, який розгалужується на два піддерева. Кожне піддерево може далі розгалужуватися на два менші піддерева, і так далі. Піддерево, яке більше не розгалужується, є гілочкою. Гілочку можна прикрасити, прикріпивши до неї не більше однієї кульки.
Рисунок 1 – Приклад дерева з піддеревами, гілочками та однією кулькою.
Прикрашене дерево має рівномірний розподіл кульок, якщо і тільки якщо виконується наступна вимога:
У кожній точці, де (під)дерево розгалужується на два менші піддерева t_1 і t_2, загальна кількість кульок у лівому піддереві N(t_1) та загальна кількість кульок у правому піддереві N(t_2) повинні бути або рівними, або відрізнятися на одну. Тобто: |N(t_1)-N(t_2)| ≤ 1.
У своєму ентузіазмі судді спочатку прикріплюють кульки до довільних гілочок на дереві. Коли вони не можуть знайти більше кульок, щоб прикріпити до дерева, вони відступають і розглядають результат. У більшості випадків розподіл кульок не зовсім рівномірний. Вони вирішують виправити це, перемістивши деякі кульки на інші гілочки.
Знаючи структуру дерева та початкове розташування кульок, обчисліть мінімальну кількість кульок, які потрібно перемістити, щоб досягти рівномірного розподілу, як визначено вище.
Зверніть увагу, що не дозволяється додавати нові кульки на дерево або назавжди видаляти кульки з дерева. Єдиний спосіб, яким дерево може бути змінено, це переміщення кульок на інші гілочки.
Вхідні дані
Для кожного тестового випадку вхід складається з одного рядка, що описує прикрашене дерево.
Опис дерева складається з рекурсивного опису його піддерев. (Під)дерево представляється рядком в одній з наступних форм:
Рядок '()' представляє гілочку без кульки.
Рядок '(B)' представляє гілочку з прикріпленою до неї кулькою.
Рядок '(t_1 t_2)' представляє (під)дерево, яке розгалужується на два менші піддерева, представлені t_1 і t_2, де t_1 і t_2 є рядками в одній з форм, наведених тут.
Дерево містить щонайменше 2 і щонайбільше 1000 гілочок.
Вихідні дані
Для кожного тестового випадку виведіть один рядок.
Якщо можливо рівномірно розподілити кульки по дереву, виведіть мінімальну кількість кульок, які потрібно перемістити, щоб задовольнити вимогу рівномірного розподілу.
Якщо неможливо рівномірно розподілити кульки, виведіть слово 'неможливо'.