← 返回题目列表

AtCoder · icpc2013spring_d

D. 医疗检查

中文机器翻译题面 查看原题

问题陈述

由于贵国 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