50分。

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

int n, m, ans = 0, sum = 0;
vector<int> a[10005];
int f[10005], cnt;
bool ff = true;
void dfs(int x, int flag)
{
	if (ff == false)
	{
		return ;
	}
	for (int i = 0; i < a[x].size(); i++)
	{
		if (f[a[x][i]] == 0)
		{
			f[a[x][i]] = flag;
			cnt++;
			dfs(a[x][i], 3 - flag);
		}
		else
		{
			if (f[a[x][i]] != flag)
			{
				ff = false;
				break;
			}
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie();cout.tie();
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
	{
		if (f[i] == 0)
		{
			f[i] = 1;
			cnt = 1;
			dfs(i, 2);
			if (cnt == 1)
			{
				f[i] = 0;
			}
		}
	}
	if (ff == false)
	{
		printf("Impossible");
		return 0;
	}
	for (int i = 1; i <= n; i++)
	{
		if (f[i] == 1)
		{
			ans++;
		}
		else if (f[i] == 2)
		{
			sum++;
		}
//		cout << f[i] << ' ';
	}
//	cout << endl;
	cout << min(ans, sum);
	return 0;
}