题目描述

政府宣布因你所在国家的 MOFU 综合症疫情而进入紧急状态。该国的人们患有 MOFU 综合症，无法在早上离开床铺。你是卫生部门的一名程序员，必须采取迅速的措施。

该国由编号为 1 到 n 的 n 个岛屿组成，并且某些岛屿之间有海洋船只。卫生部决定在一些岛屿设立隔离站，并限制感染者的活动，以防止疫情扩大。为了执行这个计划，不能有任何一艘船只在航线源头和目的地都没有隔离站。问题是由于预算不足，该部门最多只能建立 K 个隔离站。

你的任务是计算是否可能实现这个目标。如果可能，你必须计算所需的最小隔离站数量。

输入

测试用例以一行包含三个整数 $N (2 \leq N \leq 3{,}000)$、$M (1 \leq M \leq 30{,}000)$ 和 $K (1 \leq K \leq 32)$ 开始。接下来的 $M$ 行中的每行包含两个整数 $a_i (1 \leq a_i \leq N)$ 和 $b_i (1 \leq b_i \leq N)$，表示第 $i$ 条海洋船只连接岛屿 $a_i$ 和 $b_i$。对于所有 $i$，可以假设 $a_i \neq b_i$，并且所有岛屿对之间最多只有一条海洋船只。

输出

如果没有方法可以建立满足目标的隔离站，则输出 "Impossible"（不包含引号）。否则，输出所需的最小隔离站数量。

示例输入1

3 3 2
1 2
2 3
3 1

示例输出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

题目来源

Japan Alumni Group Spring Contest 2013