Building Teams

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

typedef long long ll;

const ll N = 100000;

vector<ll> adj[N];

ll visited[N] = {0};

int prev_team = 0;
bool flag = false;
int chosen_team = 1;

ll team[N] = {0};

void change_team() {
    if(chosen_team == 1) chosen_team = 2;
    else chosen_team = 1;
}

void dfs(ll s) {
    if (visited[s] == 1) {
        change_team();
        return;
    } 
    visited[s] = 1;

    //cout << " I color " << s << " as " << chosen_team << endl;
    team[s] = chosen_team;
    
    change_team();
    int tmp = chosen_team;

    //cout << " state " << s << endl;
    for (auto u: adj[s]) {
        if(team[u] == team[s]) {
            flag = true;
        }
        dfs(u);
        //cout << "I switch back to" << tmp << endl;
        chosen_team = tmp;
    }
}

int main() {
    ll n, m;
    cin >> n;
    cin >> m;

    ll a,b;
    for(ll i = 0; i<m; i++) {
        cin >> a;
        cin >> b;

        adj[a-1].push_back(b-1);
        adj[b-1].push_back(a-1);
    }

    for(ll i = 0; i<n; i++) {
        dfs(i);
        if(flag) {
            cout << "IMPOSSIBLE" << endl;
            return 0;
        }
    }

    for(ll i = 0; i<n; i++) {
        cout << team[i] << " ";
    }
    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