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];

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

void dfs(ll s) {
    if (visited[s] == 1) {
        if(prev_team == chosen_team) {
            flag = true;
        }
        return;
    } 
    visited[s] = 1;

    team[s] = chosen_team;
    change_team();

    for (auto u: adj[s]) {
        dfs(u);
    }
}

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: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER