Задача G. Головоломка

Автор:XIII командный чемпионат школьников Санкт-Петербурга по программированию   Ограничение времени:2 сек
Входной файл:puzzle.in   Ограничение памяти:32 Мб
Выходной файл:puzzle.out  

Условие

Не так давно были достаточно популярны настольные игры на больших бумажных картах, в которых игроки передвигали фишки по определенным правилам.

Недавно Вася нашел на чердаке целую кипу таких карт, но к ним, к сожалению, не прилагались правила игры. Без описаний он смог только понять, что на каждой из карт нарисовано некоторое количество кружков — возможных позиций для фишки, среди которых выделены начальная и конечная. Какие-то кружки соединены между собой отрезками, по которым разрешается перемещать фишку, при этом между некоторыми парами кружков может быть проведено сразу несколько отрезков. Перемещать фишку по отрезку разрешается в обоих направлениях.

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

Вася заинтересовался, за какое минимальное количество ходов можно добиться того, чтобы фишки на всех картах одновременно оказались в конечных позициях. Помогите ему это выяснить.

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

Формат входного файла

Первая строка входного файла содержит число k — количество карт. Затем следуют k блоков, которые описывают карты. Первая строка каждого блока содержит два целых числа ni и mi, они задают количество позиций и количество отрезков на i-й карте, соответственно. Будем считать, что позиции пронумерованы числами от 1 до ni, причем начальная позиция имеет номер 1, а конечная — номер ni. В следующих mi строках находятся пары номеров позиций, соединенных соответствующим отрезком.

Формат выходного файла

В случае, если существует последовательность ходов, после которой фишки на каждой карте одновременно окажутся в конечных состояниях, выведите в выходной файл минимальную длину такой последовательности. Если такой последовательности не существует, выведите слово Impossible.

Ограничения

1 ≤ k ≤ 10, 2 ≤ ni ≤ 50, 1 ≤ mi ≤ 1500

Примеры тестов

Входной файл (puzzle.in) Выходной файл (puzzle.out)
1
2
5 4
1 2
2 3
3 4
3 5
3 3
1 2
2 3
3 1
3

0.035s 0.008s 15