ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2002

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Cockroaches!

Time limit: 1.0 second
Memory limit: 64 MB
It's well-known that the most tenacious of life species on the Earth are cockroaches. They live everywhere if only there in food. And as far as they are unpretentious in food you can find them absolutely everywhere.
A little Lyosha studies at school on a Space station. During one of the school competitions his class has reached the final. A task of the final contest is to exterminate all the cockroaches in the cargo module within minimal time.
Within the long history of the competitions a unified tactics was worked out. The tactics is as follows: a poison gas is let in one of the module compartments and after that the baffle that separates the compartment from one of the adjacent ones is opened.  Cockroaches can't stand the smell of the gas and run to the other compartment. When there's no cockroaches in the treated compartment the baffle is closed. Afterwards analogously the next compartment is treated, and so on. The goal is to move all the cockroaches to the floodgate of the cargo module. Then the outward door is opened and all the cockroaches are engulfed by an open Space.
Lyosha is responsible for programming the control board of the baffles in his team. The baffles are opened slowly, so it's very important to make do with minimal number of baffle openings in order to win in the contest. Your task is to help Lyosha to compute this number.


The first line contains a name of the floodgate compartment. Each of the next lines contains description of one of the baffles — the names of two compartments separated with a dash (-). The last line contains the only symbol "#". There are cockroaches in all the compartments of the module at first. It's possible to get to the floodgate from every compartment of the module passing several baffles. The total number of compartments doesn't exceed 30. The name of a compartment consists of no more than 20 Latin letters and digits. The large and the small letters should be distinguished.


Your program is to output the only number — the minimal amount of baffles that should be opened (and then closed) in order to move all the cockroaches to the floodgate.


Problem Author: Eugeny Krokhalev
Problem Source: USU Open Collegiate Programming Contest October'2002 Junior Session
To submit the solution for this problem go to the Problem set: 1213. Cockroaches!