228E - The Road to Berland is Paved With Good Intentions - CodeForces Solution

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

int n, m, u, v, ans = 0;
bool w, c[101], vi[101];
struct edge{
	int u, v;
	bool w;
};
vector<pair<int, bool>> g[101];
vector<edge> e;
queue<int> q;

void bfs(int s) {
	vi[s] = true; q.push(s);
	while (!q.empty()) {
		u = q.front();
		q.pop();
		for (auto [v, w] : g[u]) if (!vi[v])
			vi[v] = true, c[v] = w ^ c[u], q.push(v);
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	while (m--) {
		cin >> u >> v >> w; w = !w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
		e.push_back({u, v, w});
	}
	for (int i = 1; i <= n; i++) if (!vi[i]) bfs(i);
	for (auto [u, v, w] : e) if (c[u] ^ c[v] != w)
		return cout << "Impossible", 0;
	for (int i = 1; i <= n; i++) ans += c[i];
	cout << ans << '\n';
	for (int i = 1; i <= n; i++) if (c[i]) cout << i << ' ';
	return 0;
}