검역소 설치

시간 제한10초메모리 제한512 MB

요약

모든 항로가 검역소가 있는 섬과 닿도록 K개 이하로 섬을 고르고 그 최소 개수를 구합니다.

난이도: 보통10점 중 7점
유형: 백트래킹, 그래프
정답자: 아직 제출이 없습니다

문제

당신의 나라에 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을 출력한다. 있으면 필요한 검역소의 최소 개수를 출력한다.

예제4

예제 1
입력
```
3 3 2
1 2
2 3
3 1
```
예상 출력
```
2
```
예제 2
입력
```
3 3 1
1 2
2 3
3 1
```
예상 출력
```
Impossible
```
예제 3
입력
```
7 6 5
1 3
2 4
3 5
4 6
5 7
6 2
```
예상 출력
```
4
```

예제 4

입력

예상 출력