①每一条边所连接的点中，至少要有一个被选中。②每一条边所连接的两个点，不能被同时选中。由此，可以推断出：

每一条边都有且仅有一个被它所连接的点被选中。

又因为我们要处理的是一个连通图。所以，对于这一个图的点的选法，可以考虑到相邻的点染成不同的颜色。

于是，对于一个连通图，要不就只有两种选法（因为可以全部选染成一种色的，也可以全部选染成另一种色的），要不就是impossible！

-------KesdiaelKen dalao

其实就是普通bfs（逃

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;queue 
          
            q;int n,m,x,y;int ans;int now;int now_2;int now_3;struct E { int to; int next;} edge[200010];int e_sum=0;int col[10010];int point[10010];bool foot[10010];void add(int from,int to) { ++e_sum; edge[e_sum].to=to; edge[e_sum].next=point[from]; point[from]=e_sum; return;}void bfs(int s) { if(foot[s]==true) return; foot[s]=true; now_2=0; now_3=0; q.push(s); col[s]=2; ++now_2; while(!q.empty()) { now=q.front(); q.pop(); for(int i=point[now]; i!=0; i=edge[i].next) { if(col[edge[i].to]==0) { col[edge[i].to]=col[now]^1; if(col[edge[i].to]==2) ++now_2; else ++now_3; q.push(edge[i].to); foot[edge[i].to]=true; } else if(col[edge[i].to]==col[now]) { cout<<"Impossible"; exit(0); } } } ans+=min(now_2,now_3); return;}int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1; i<=m; i++) { cin>>x>>y; add(x,y); add(y,x); } for(int i=1; i<=n; i++) bfs(i); cout<