P1330 Locking Down Sunshine University

Cao is a veteran who loves cruising around. During the summer break, he happily cruises through the campus streets of Sunshine University every day. The He Xie (河蟹) feel annoyed seeing happy Cao and decide to lock down Sunshine University so that Cao cannot cruise around. The campus of Sunshine University is an undirected graph with $n$ vertices connected by $m$ roads. Each He Xie can block one vertex. When a vertex is blocked, all roads incident to this vertex are blocked, and Cao cannot cruise on those roads. Unfortunately, the He Xie are disharmonious creatures: if two He Xie block two adjacent vertices, they will get into a conflict. Question: What is the minimum number of He Xie needed to block all roads without any conflicts?

The first line contains two positive integers, the number of vertices and the number of edges. Then $m$ lines follow. Each line contains two integers $u, v$, indicating that there is a road between vertices $u$ and $v$.

Output a single line. If the He Xie cannot block all roads, output `Impossible`. Otherwise, output a single integer, the minimum number of He Xie required.

Constraints For $100\%$ of the testdata, $1 \le n \le 10^4$, $1 \le m \le 10^5$, and there are no multiple edges. Translated by ChatGPT 5