Задача №1776. Головоломка
Не так давно были достаточно популярны настольные игры на больших бумажных картах, в которых игроки передвигали фишки по определенным правилам.
Недавно Вася нашел на чердаке целую кипу таких карт, но к ним, к сожалению, не прилагались правила игры. Без описаний он смог только понять, что на каждой из карт нарисовано некоторое количество кружков – возможных позиций для фишки, среди которых выделены начальная и конечная. Какие-то кружки соединены между собой отрезками, по которым разрешается перемещать фишку, при этом между некоторыми парами кружков может быть проведено сразу несколько отрезков. Перемещать фишку по отрезку разрешается в обоих направлениях.
Поскольку правила игры Васе найти не удалось, он придумал свои собственные. В игре участвуют одновременно все карты. На каждой карте Вася использует ровно одну фишку. Изначально каждая фишка расположена в начальной позиции на соответствующей карте. Каждым ходом Вася перемещает фишку на каждой из карт из ее текущей позиции в некоторую другую позицию на этой карте, с которой текущая соединена отрезком. При этом даже если фишка на некоторой карте уже находится в конечной позиции, то Вася, делая очередной ход, все равно должен ее переместить.
Вася заинтересовался, за какое минимальное количество ходов можно добиться того, чтобы фишки на всех картах одновременно оказались в конечных позициях. Помогите ему это выяснить.
Гарантируется, что в пределах каждой карты из любой позиции можно переместить фишку в любую другую, возможно через некоторые промежуточные позиции.
Первая строка входного файла содержит число \(k\) – количество карт (1 ≤ \(k\) ≤ 10).
Затем следуют \(k\) блоков, которые описывают карты. Первая строка каждого блока содержит два целых числа \(n_i\) и \(m_i\) (2 ≤ \(n_i\) ≤ 50, 1 ≤ \(m_i\) ≤ 1500), они задают количество позиций и количество отрезков на \(i\)-й карте, соответственно. Будем считать, что позиции пронумерованы числами от 1 до \(n_i\), причем начальная позиция имеет номер 1, а конечная – номер \(n_i\). В следующих \(m_i\) строках находятся пары номеров позиций, соединенных соответствующим отрезком.
В случае, если существует последовательность ходов, после которой фишки на каждой карте одновременно окажутся в конечных состояниях, выведите в выходной файл минимальную длину такой последовательности. Если такой последовательности не существует, выведите слово «Impossible».
2 5 4 1 2 2 3 3 4 3 5 3 3 1 2 2 3 3 1
3