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
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