Building Teams

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>

using namespace std;

using ll  = long long;
using vi  = vector<int>;
using vc = vector<char>;
using vll = vector<long long>;
using vs  = vector<string>;
using vb = vector<bool>;
using vvi  = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vvc  = vector<vector<char>>;
using vvb  = vector<vector<bool>>;
using pii = pair<int, int>;


#define all(x) (x).begin(), (x).end()
#define pb push_back
#define sz(x) ((int)(x).size())
#define forn(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int n, m;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> m;
  vvi adj(n+1);
  int a, b;
  forn(i, m){
    cin >> a >> b;
    adj[a].pb(b);
    adj[b].pb(a);
  }

  vi teams(n+1, 0);

  for(int i = 1; i <= n; i++){

    if(teams[i] != 0) continue; //ya tiene equipo

    queue<int> q;
    q.push(i);
    teams[i] = 1;

    while(not q.empty()){
      int node = q.front();
      q.pop();

      for(auto v : adj[node]){
        if(teams[v] == 0){
          teams[v] = 3-teams[node];
          q.push(v);
        }
        else if(teams[v] == teams[node]){
          cout << "IMPOSSIBLE" << endl;
          return 0;
        }
      }
    }
  }

  for(int i = 1; i <=n; i++) cout << teams[i] << (i == n ? "" : " ");
  cout << endl;
}

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