퍼즐

얼마 전까지 큰 종이 지도 위에서 규칙에 따라 말을 움직이는 보드 게임이 꽤 인기를 끌었다.

최근에 바샤는 다락방에서 그런 지도를 한 무더기 발견했지만, 안타깝게도 게임 규칙은 함께 들어 있지 않았다. 설명이 없어서 그가 알아낸 것은 각 지도에 말이 놓일 수 있는 위치인 원이 여러 개 그려져 있고, 그중 시작 위치와 끝 위치가 표시되어 있다는 정도였다. 일부 원은 선분으로 이어져 있고, 말은 그 선분을 따라 움직일 수 있으며, 어떤 원 쌍 사이에는 선분이 여러 개 그어져 있을 수도 있다. 말은 선분을 양방향으로 움직일 수 있다.

게임 규칙을 찾지 못한 바샤는 자신만의 규칙을 만들었다. 게임에는 모든 지도가 동시에 참여한다. 바샤는 각 지도에서 말을 정확히 하나씩 사용한다. 처음에 각 말은 해당 지도에서 시작 위치에 놓인다. 바샤는 매 턴마다 모든 지도에서 말을 현재 위치에서 그 지도 안의 다른 위치로 옮기는데, 그 위치는 현재 위치와 선분으로 이어져 있어야 한다. 어떤 지도의 말이 이미 끝 위치에 있더라도, 바샤는 다음 턴에도 그 말을 반드시 옮겨야 한다.

바샤는 모든 지도의 말이 동시에 끝 위치에 놓이게 하려면 최소 몇 턴이 필요한지 궁금해졌다. 그가 알아낼 수 있도록 도와주자.

각 지도 안에서는 어떤 위치에서든 말을 다른 어떤 위치로도 옮길 수 있음이 보장된다. 중간 위치를 거쳐야 할 수도 있다.

첫째 줄에 지도의 수 $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>>을 출력한다.