我们只要知道我们一个联通块中的点要么没有被河蟹占着，要么就要有河蟹，这不就是染色问题吗，我们只要取其中的最小值加到我们答案中就行，如果相邻的边颜色一样，就无解
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;const int N = (int)1e4+5;
const int M = (int)1e5+5;
int n,m;
int e[M*2],ne[M*2],h[N],idx = 0;
int record[N];
int cnt = 0;
int co[N],vis[N];// co是为了记录染色情况，vis是记录是否纳入考虑
int num1,num2;
int flag = 0;void add(int a,int b){e[++idx] = b, ne[idx] = h[a] , h[a] = idx;
}// 我只是疑惑多个联通块的 1 2 怎么算
void dfs(int node,int fa,int color){co[node] = color; vis[node] = 1;if(color==1) num1++;else num2++;for(int i=h[node];i;i=ne[i]){int to = e[i];if(vis[to]){if(co[to]==color&&to!=fa) {flag = 1;return;}continue;}dfs(to,node,abs(color-3));}
}int main(){cin >> n >> m;for(int i=1;i<=m;i++){int u,v;cin >> u >> v;add(u,v);add(v,u);}int ans = 0;for(int i=1;i<=n;i++){num1 = 0, num2 = 0;if(!vis[i])dfs(i,0,1);if(flag) {cout << "Impossible";
// for(int i=1;i<=n;i++){
// cout <<" i " << i << " co " << co[i] << endl;
// }return 0;}ans += (min(num1,num2));}cout << ans;return 0;
}
