Building Teams

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

vector<int> A[200'001];
int Z[200'001];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		A[a-1].push_back(b-1);
		A[b-1].push_back(a-1);
	}
	queue<pair<int,int>> q;
	for (int i = 0; i < n; ++i) {
		if (Z[i]) continue;
		q.push({i,1});
		Z[i] = 1;
		while (!q.empty()) {
			auto [j,w] = q.front();
			w = w == 1 ? 2 : 1;
			q.pop();
			for (int k : A[j]) {
				if (!Z[k]) {
					q.push({k,w});
					Z[k] = w;
				} else if (Z[k] != w) {
					cout << "IMPOSSIBLE\n";
					return 0;
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		cout << Z[i] << ' ';
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED