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 веточек.
Выходные данные
Для каждого теста выведите одну строку.
Если возможно равномерно распределить шары по дереву, выведите минимальное количество шаров, которые необходимо переместить, чтобы удовлетворить требование равномерного распределения.
Если невозможно равномерно распределить шары, выведите слово 'impossible'.