검역소 설치

당신의 나라에 MOFU 증후군이 퍼져 정부가 국가 비상사태를 선포했다. 이 병에 걸린 사람은 아침에 침대에서 일어나지 못한다. 보건부에서 일하는 프로그래머인 당신이 서둘러 대책을 마련해야 한다.

나라는 1번부터 $N$번까지 번호가 붙은 $N$개의 섬으로 이루어져 있고, 일부 섬 쌍 사이에는 여객선 항로가 있다. 보건부는 감염자의 이동을 막으려고 몇몇 섬에 검역소를 세우기로 했다. 이 계획이 성립하려면 양쪽 끝 섬 모두에 검역소가 없는 항로가 하나도 없어야 한다. 문제는 예산이 부족해서 검역소를 최대 $K$개까지만 지을 수 있다는 점이다.

조건을 만족하도록 검역소를 배치할 수 있는지 판정하고, 배치할 수 있으면 필요한 검역소의 최소 개수를 구하라.

첫째 줄에 세 정수 $N$, $M$, $K$가 주어진다 ($2 \le N \le 3000$, $1 \le M \le 30000$, $1 \le K \le 32$).

다음 $M$개의 줄에는 각각 두 정수 $a_i$와 $b_i$가 주어진다 ($1 \le a_i \le N$, $1 \le b_i \le N$). $i$번째 항로가 섬 $a_i$와 섬 $b_i$를 잇는다는 뜻이다. 모든 $i$에 대해 $a_i \ne b_i$이고, 어떤 두 섬 사이에도 항로는 최대 하나다.

조건을 만족하는 검역소 배치가 없으면 Impossible을 출력한다. 있으면 필요한 검역소의 최소 개수를 출력한다.