Building Teams

#include <iostream>
#include <vector>

const int maxN = 1e5+1;

int n, m;
std::vector<int> friendships[maxN];
bool teams[maxN] = {true};
bool visited[maxN] = {false};
bool possible = true; 

void dfs(int current_node, int previous_node = 0) {
    
    for (int f : friendships[current_node]) {

        if (f != previous_node) {
            if (!visited[f]) {
                teams[f] = !teams[current_node];
                visited[f] = true;
                dfs(f, current_node);       
            } 
        }
        else {
            if (teams[f] == teams[current_node]) {
                possible = false;
            }
        }
    }
    
}

int main() {
    
    std::cin >> n >> m;

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

        a--, b--; // index of pupils starts at 1
        friendships[a].push_back(b);
        friendships[b].push_back(a);
    }
    
    // start dfs
    for (int i = 0; i < n; i++) {
        
        if (!visited[i]) {
            visited[i] = true;
            dfs(i);
        }
    }

    if (!possible) {
        std::cout << "IMPOSSIBLE" << std::endl;
        return 0;
    }    

    for (int i = 0; i< n; i++) {
        if (teams[i] == true) std::cout << "1" << " ";
        else std::cout << "2" << " ";
    }
    std::cout << "\n";

    return 0;
}

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