Quarantine Station Placement

Time limit10sMemory limit512 MB

Summary

Place quarantine stations on the fewest islands so every liner touches a station, or report that K stations cannot cover all liners.

Level: Medium7 of 10
Topics: Backtracking, Graph
Solved: No attempts yet

Problem

Your country declared a state of emergency because MOFU syndrome is spreading. Anyone who catches it cannot get out of bed in the morning. You are a programmer at the Department of Health, and you have to put a measure in place quickly.

The country has $N$ islands numbered from 1 to $N$ , and ocean liners run between some pairs of islands. The Department of Health decided to build quarantine stations on a few islands and stop infected people from travelling. For the plan to work, there must be no liner whose two endpoint islands both lack a quarantine station. The trouble is that the budget covers at most $K$ stations.

Decide whether such a placement exists. If it does, find the smallest number of quarantine stations it needs.

Input

The first line contains three integers $N$ , $M$ , and $K$ ( $2 \le N \le 3000$ , $1 \le M \le 30000$ , $1 \le K \le 32$ ).

Each of the next $M$ lines contains two integers $a_i$ and $b_i$ ( $1 \le a_i \le N$ , $1 \le b_i \le N$ ). This means the $i$ -th liner connects island $a_i$ and island $b_i$ . For every $i$ , $a_i \ne b_i$ , and at most one liner runs between any pair of islands.

Output

If no placement of quarantine stations satisfies the requirement, print Impossible. Otherwise print the smallest number of quarantine stations.

Examples4

Example 1
Input
```
3 3 2
1 2
2 3
3 1
```
Expected output
```
2
```
Example 2
Input
```
3 3 1
1 2
2 3
3 1
```
Expected output
```
Impossible
```
Example 3
Input
```
7 6 5
1 3
2 4
3 5
4 6
5 7
6 2
```
Expected output
```
4
```

Example 4

Input

Expected output