Building Teams

#include <iostream>
#include <vector>
using namespace std;

bool dfs(vector<vector<int>> &g, vector<int>& assignment, int node, int team){
    if (assignment[node]){
        if (assignment[node]==team){
            return true;
        } else {
            return false;
        }
    }
    assignment[node]=team;
    for (int next: g[node]){
        if (!dfs(g, assignment, next, team==1? 2 :1)){
            return false;
        }
    }
    return true;
}

int main(){
    int n, m;

    cin >> n >> m;
    vector<vector<int>> g(n+1, vector<int>(0));
    for (int i=0;i<m;i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> assignment(n+1, 0);

    for (int i=1;i<=n;i++){
        if (!assignment[i]){
            if (!dfs(g, assignment, i, 1)) {
                cout << "IMPOSSIBLE\n";
                return 0;
            }
        }
    }
    for (int i=1;i<=n;i++){
        cout << assignment[i] << ' ';
    }
    cout << '\n';
    return 0;
}

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