P1330 封锁阳光大学

题目描述

给出一张由 $n$ 个点 $m$ 条边 构成的无向图。

选中最少的点，使得所有的边都被封锁。

规则：

1、当某个点被选中后，与这个点相连的无向边就被封锁了。

2、不能选中相邻的两个点。

输入格式

第一行两个正整数 $n,m$，表示节点数和边数。 接下来 $m$ 行，每行两个整数 $u,v$，表示点 $u$ 到点 $v$ 之间有边相连。

输出格式

仅一行，如果无法封锁所有边，则输出 Impossible，否则输出一个整数，表示最少需要选中的点数。

输入输出样例 #1

输入 #1

3 3
1 2
1 3
2 3

输出 #1

Impossible

输入输出样例 #2

输入 #2

3 2
1 2
2 3

输出 #2

1

说明/提示

【数据规模】
对于 $100\%$ 的数据，$1\le n \le 10^4$，$1\le m \le 10^5$，保证没有重边。