시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 21 2 2 9.524%

문제

The government has declared a state of emergency due to the MOFU syndrome epidemic in your country. Persons in the country suffer from MOFU syndrome and cannot get out of bed in the morning. You are a programmer working for the Department of Health. You have to take prompt measures.

The country consists of n islands numbered from 1 to n and there are ocean liners between some pair of islands. The Department of Health decided to establish the quarantine stations in some islands and restrict an infected person's moves to prevent the expansion of the epidemic. To carry out this plan, there must not be any liner such that there is no quarantine station in both the source and the destination of the liner. The problem is the department can build at most K quarantine stations due to the lack of budget.

Your task is to calculate whether this objective is possible or not. And if it is possible, you must calculate the minimum required number of quarantine stations.

입력

The test case starts with a line containing three integers N(2 ≤ N ≤ 3,000), M(1 ≤ M ≤ 30,000) and K(1 ≤ K ≤ 32). Each line in the next M lines contains two integers ai(1 ≤ ai ≤ N) and bi(1 ≤ bi ≤ N). This represents i-th ocean liner connects island ai and bi. You may assume ai ≠ bi for all i, and there are at most one ocean liner between all the pairs of islands.

 

출력

If there is no way to build quarantine stations that satisfies the objective, print "Impossible" (without quotes). Otherwise, print the minimum required number of quarantine stations.

예제 입력

3 3 2
1 2
2 3
3 1

예제 출력

2

예제 입력 2

3 3 1
1 2
2 3
3 1

예제 출력 2

Impossible

예제 입력 3

7 6 5
1 3
2 4
3 5
4 6
5 7
6 2

예제 출력 3

4

예제 입력 4

10 10 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

예제 출력 4

4

힌트