Building Teams

#include <iostream>
#include <vector>
#include <queue>

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

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

    std::vector<int> group_nr(n);

    std::queue<int> search_queue;
    std::vector<bool> visited(n, false);
    int last_new_component = 0;

    for (int i = 0; i < n; ++i) {
        if (search_queue.empty()) {
            for (int j = last_new_component; j < n; ++j) {
                if (visited[j]) continue; 
                search_queue.push(j);
                visited[j] = true;
                last_new_component = j;
                group_nr[j] = 0;
                break;
            }
        }

        int person = search_queue.front();
        search_queue.pop();
        int group = group_nr[person];
        for (auto new_person : friends[person]) {
            if (visited[new_person]) {
                if (group_nr[new_person] == group) {
                    std::cout << "IMPOSSIBLE" << std::endl;
                    return 0;
                }
                continue;
            } 

            search_queue.push(new_person);
            visited[new_person] = true;
            group_nr[new_person] = 1 - group;
        }
    }

    for (int i = 0; i < n; ++i) {
        std::cout << group_nr[i]+1 << " ";
    }
    std::cout << std::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