| Автор: | XIII командный чемпионат школьников Санкт-Петербурга по программированию | Ограничение времени: | 2 сек | |
| Входной файл: | puzzle.in | Ограничение памяти: | 32 Мб | |
| Выходной файл: | puzzle.out |
Не так давно были достаточно популярны настольные игры на больших бумажных картах, в которых игроки передвигали фишки по определенным правилам.
Недавно Вася нашел на чердаке целую кипу таких карт, но к ним, к сожалению, не прилагались правила игры. Без описаний он смог только понять, что на каждой из карт нарисовано некоторое количество кружков — возможных позиций для фишки, среди которых выделены начальная и конечная. Какие-то кружки соединены между собой отрезками, по которым разрешается перемещать фишку, при этом между некоторыми парами кружков может быть проведено сразу несколько отрезков. Перемещать фишку по отрезку разрешается в обоих направлениях.
Поскольку правила игры Васе найти не удалось, он придумал свои собственные. В игре участвуют одновременно все карты. На каждой карте Вася использует ровно одну фишку. Изначально каждая фишка расположена в начальной позиции на соответствующей карте. Каждым ходом Вася перемещает фишку на каждой из карт из ее текущей позиции в некоторую другую позицию на этой карте, с которой текущая соединена отрезком. При этом даже если фишка на некоторой карте уже находится в конечной позиции, то Вася, делая очередной ход, все равно должен ее переместить.
Вася заинтересовался, за какое минимальное количество ходов можно добиться того, чтобы фишки на всех картах одновременно оказались в конечных позициях. Помогите ему это выяснить.
Гарантируется, что в пределах каждой карты из любой позиции можно переместить фишку в любую другую, возможно через некоторые промежуточные позиции.
| № | Входной файл (puzzle.in) |
Выходной файл (puzzle.out) |
|---|---|---|
| 1 | |
|