Хорошо известно, что самым живучим биологическим видом на Земле являются тараканы. Они живут всюду, где можно найти еду. А поскольку в еде они неприхотливы, то живут они просто везде.

Маленький Леша учится в школе на космической станции. Во время одного из школьных состязаний его класс вышел в финал. Задание финального конкурса заключается в том, чтобы как можно быстрее выморить всех тараканов в грузовом модуле.

За долгую историю проведения состязаний у школьных команд выработалась единая тактика в этом конкурсе. Тактика такова: в один из отсеков модуля запускается ядовитый газ, после этого открывается одна перегородка, соединяющая этот отсек с одним из соседних. Тараканы, не выдерживая запаха газа, перебегают в соседнее помещение. После того, как в обработанном отсеке не останется ни одного таракана, перегородка закрывается. Далее аналогичным образом обрабатывается другой отсек и т.д. Главная цель — загнать всех тараканов в шлюзовой отсек грузового модуля. Тогда открывается внешняя дверь и, со свистом и визгом, тараканов засасывает в открытый космос.

В своём классе Леша как раз отвечает за программирование пульта управления перегородками. Перегородки открываются довольно медленно, поэтому для победы в конкурсе важно обойтись минимально возможным количеством подъемов перегородок. Ваша задача состоит в том, чтобы помочь Леше подсчитать такое минимальное количество.

В первой строке записано название шлюзового отсека. Каждая следующая строка содержит описание одной из перегородок — название двух отсеков, разделенных дефисом. Последняя строка содержит всего один символ: "#". Тараканы живут во всех отсеках грузового модуля. Из любого отсека можно пройти в шлюзовой отсек, пройдя через несколько перегородок. Общее количество отсеков не превышает 30. Название отсека состоит не более чем из 20 латинских букв и цифр, большие и маленькие буквы следует различать. В начальный момент времени все перегородки закрыты.

Выведите минимальное количество перегородок, которые надо открыть (а потом закрыть), чтобы перегнать всех тараканов в шлюзовый отсек.