2584. 干扰者病毒

1000ms 256MB 简单 图的基本应用
题目描述
在 M 星球上建立了很多通信基站,这些基站组成了通信网络。 近期出现了一种名为“干扰者”的病毒,它们能够侵入并破坏基站之间的通信。 通信网络可以看作由 $n$ 个基站构成的无向图,基站编号为 $1 \sim n$,通过 $m$ 条线路相连。每个“干扰者”病毒都可以选择一个基站进行破坏,当某个基站被破坏后,与这个基站相连的线路就会被切断。 但病毒有个奇妙的现象:如果它们选择了相邻的两个基站,就会产生冲突。 请你找出至少需要多少个“干扰者”病毒,才能切断所有线路并避免病毒冲突。
输入格式
第一行两个正整数 $n$ 和 $m$,分别表示基站的数量和线路的数量。 接下来 $m$ 行,每行包含两个整数 $u$ 和 $v$,表示基站 $u$ 和基站 $v$ 之间存在一条线路。
输出格式
如果“干扰者”病毒无法切断所有线路,则输出 `Impossible`;否则输出一个整数,表示至少需要多少个“干扰者”病毒。
样例 1
输入 (Input)

                    
输出 (Output)

                    
样例 2
输入 (Input)

                    
输出 (Output)

                    
任选一点开始放置病毒,满足题意表示线路都被切断,否则不存在。
自测终端 stdin → stdout
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout

                
错误 stderr

                
CtrlEnter提交
自动保存已开启
操作成功
wzs_oj@kernel:~ — wzs-sh
guest@wzsoj:~$
刷新页面 F5
复制 Ctrl+C
粘贴 Ctrl+V
搜索题目
训练中心
站点公告
今日神谕
CSP 倒计时
排行榜
我的提交
Esc 关闭 Enter 跳转 支持模糊匹配数字