Building Teams

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool dfs(int pupil, int team, vector<int> &teams, vector<vector<int>> &friendships) {
    teams[pupil] = team; 

    for(auto fr : friendships[pupil]) {
        if(teams[fr] == team) {
            return false;
        }
        else if(teams[fr] == -1) {
            int other_team;
            if (team == 1)
                other_team = 2;
            else
                other_team = 1;

            if(!dfs(fr, other_team, teams, friendships))
                return false;
        }
    }
    return true;
}

int main() {

    int n, m;
    cin >> n >> m;
 
    vector<vector<int>> friendships(n+1);
 
    // Read friendships
    for (int i = 0; i < m; ++i) {
        int f1, f2;
        cin >> f1 >> f2;
        friendships[f1].push_back(f2);
        friendships[f2].push_back(f1);
    }
    
    vector<int> teams(n+1, -1);

    for(int i = 1; i <= n; i++) {
        if(teams[i] == -1) { 
            if(!dfs(i, 1, teams, friendships) and !dfs(i, 2, teams, friendships))
                cout << "IMPOSSIBLE" << endl; 
        }
    }
    
    for (int i = 1; i <= n; ++i)
        cout << teams[i] << " ";
    cout << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER