rt，二分图，考虑了不连通

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1e4+5;
vector<int> t[maxn];
int dis[maxn];
int n,m,ans=0;
bool bfs(){
	queue<int> q;
	memset(dis,0,sizeof dis);
	int c1=0,c2=0;
	for(int i=1;i<=n;i++){
		if(dis[i]==0){
			q.push(i);
			dis[i]=1;
			while(!q.empty()){
				int d=q.front();
				q.pop();
				for(auto it:t[d]){
					if(dis[it]==0){
						dis[it]=-dis[d];
						q.push(it);
						if(dis[it]==1){
							c1++;
						}else{
							c2++;
						}
					}else if(dis[it]==dis[d]){
						return false;
					}
				}
			}
		}
	}
	ans+=min(c1,c2);
	return true;
}
int main(){
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin >> u >> v;
		t[u].push_back(v);
		t[v].push_back(u);
	}
	if(!bfs())cout << "Impossible";
	else cout << ans;
	return 0;
}