5043 - 图论:二分图:封锁

通过次数

2

提交次数

6

时间限制 : 1 秒
内存限制 : 128 MB

科技大学的校园是一张由 n 个点构成的无向图, n 个点之间由 m 条道路连接。每个保安可以对一个点进行封锁,当某个点被封锁后,与这个点相连的道路就被封锁了,学生就无法在这些道路上刷街了。非常悲剧的一点是,保安对互相冲突,当两个保安封锁了相邻的两个点时,他们会发生冲突。

询问:最少需要多少个保安,可以封锁所有道路并且不发生冲突。

输入

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

输出

仅一行如果保安无法封锁所有道路,则输出 Impossible,否则输出一个整数,表示最少需要多少保安。

样例

输入

3 3
1 2
1 3
2 3

输出

Impossible

输入

3 2
1 2
2 3

输出

1

提示

【数据规模】 对于 100% 的数据,1≤n≤10^4 1≤m≤10^5 ,不保证没有重边。