21435번 - Головоломка 다국어

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

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

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

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

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

Первая строка входного файла содержит число $k$ --- количество карт ($1 \le k \le 10$).

Затем следуют $k$ блоков, которые описывают карты. Первая строка каждого блока содержит два целых числа $n_i$ и $m_i$ ($2 \le n_i \le 50$, $1 \le m_i \le 1500$), они задают количество позиций и количество отрезков на $i$-й карте, соответственно. Будем считать, что позиции пронумерованы числами от 1 до $n_i$, причем начальная позиция имеет номер $1$, а конечная --- номер $n_i$. В следующих $m_i$ строках находятся пары номеров позиций, соединенных соответствующим отрезком.

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