12098 干扰者病毒

题目描述

在 M 星球上建立了很多通信基站，这些基站组成了通信网络。

近期出现了一种名为“干扰者”的病毒，它们能够入侵并破坏基站间的通信。

通信网络可以看作是由 $n$ 个基站构成的无向图，基站编号从 $1$ 到 $n$，通过 $m$ 条线路相连。每个“干扰者”病毒都可以选择一个基站进行破坏，当某个基站被破坏后，与这个基站相连的线路就会被切断。但病毒有个奇妙的现象，如果它们选择了相邻的两个基站，就会产生冲突。

请你找出至少需要多少个“干扰者”病毒，才能切断所有线路并避免病毒冲突。

提示：任选一点开始放置病毒，满足则表示线路能全部切断，相反则不存在。

输入格式

第一行两个正整数 $n$ 和 $m$，分别表示基站的数量和线路的数量。

接下来 $m$ 行，每行两个整数 $u$ 和 $v$，表示基站 $u$ 和基站 $v$ 之间存在一条线路。

输出格式

如果“干扰者”病毒无法封锁所有线路，则输出 Impossible；否则，输出一个整数，表示至少需要多少个“干扰者”病毒。

样例输入 #1

3 3
1 2
1 3
2 3

样例输出 #1

Impossible

样例输入 #2

3 2
1 2
3 2

样例输出 #2

1

样例输入 #3

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

样例输出 #3

3

数据范围

$1 \le n, m \le 1000$

时间限制：1000MS，空间限制：128MB。

知识点与难度

本题涉及的知识点从属于 GESP七级（图的存储与遍历、二分图判定、BFS 染色、贪心统计），难度等级：⭐⭐⭐⭐。

测试点分布