50分WA on #23457求条

#include <bits/stdc++.h>
using namespace std;

int n, m;

vector<int> e[10001];
int color[10001];
bool vis[10001];

void bfs(int x) {
	queue<int> q;
	q.push(x);
	color[x] = 1;
	while (!q.empty()) {
		int t = q.front();
		q.pop();
		vis[t] = true;
		for (int s : e[t]) {
			int col = !color[t];
			if (!vis[s]) {
				color[s] = col;
				q.push(s);
			} else if (color[s] == color[t]) {
				cout << "Impossible";
				exit(0);
			}
		}
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {//  处理非连通块
		if (!vis[i]) {
			bfs(i);
		}
	}
	int cnt1 = 0, cnt0 = 0;
	for (int i = 1; i <= n; i++) {
		if (color[i] == 1) {
			cnt1++;
		} else {
			cnt0++;
		}
	}
	cout << min(cnt1, cnt0);
	return 0;
}