5043 - 图论:二分图:封锁
时间限制 : 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 ,不保证没有重边。