Building Teams

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   // freopen("input.txt", "r", stdin); // TODO: REMOVE THIS YOU STUPID ****

   int n, m;
   cin >> n >> m;
   vector<vector<int>> edges(n+1);
   for (int i = 0; i < m; i++) {
      int a, b;
      cin >> a >> b;
      edges[a].push_back(b);
      edges[b].push_back(a);
   }
   vector<bool> visited(n+1, false);
   vector<int> colors(n+1, -1);
   queue<int> q;

   for (int i = 1; i < n+1; i++) {
      if (visited[i]) continue;
      visited[i] = true;
      q.push(i);
      colors[i] = 1;
      while (!q.empty()) {
         int node = q.front(); q.pop();
         int color = colors[node];
         for (auto& u : edges[node]) {
            if (colors[u] == color) {
               cout << "IMPOSSIBLE";
               return 0;
            }
            if (visited[u]) continue;
            visited[u] = true;
            q.push(u);
            colors[u] = color == 1 ? 2 : 1;
         }
      }
   }
   for (int i = 1; i < n+1; i++) {
      cout << colors[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