问题陈述
由于贵国 MOFU 综合症的流行,政府已宣布进入紧急状态。 国内的人患有MOFU综合症,早上起不来床。 您是一名为卫生部工作的程序员。你必须迅速采取措施。
该国家由 n 岛屿编号从 1 到 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。 你可能会假设 a_i \neq b_i 对于所有人 i,并且所有两对岛屿之间最多有一艘远洋客轮。
输出
如果无法建立满足目标的检疫站,请打印“不可能”(不带引号)。否则,打印所需的最少检疫站数量。
示例输入 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