Building Teams

#include <iostream>
#include <vector>

int main()
{
    int n_pupils, n_friendships;
    std::cin >> n_pupils >> n_friendships;
    
    std::vector<std::vector<int>> adjacencies(n_pupils);
    std::vector<bool> teams(n_pupils, false);
    std::vector<bool> init(n_pupils, false);
    std::vector<bool> discovered(n_pupils, false);
    
    for (int i = 0; i < n_friendships; i++)
    {
        int a, b;
        std::cin >> a >> b;
        a--;
        b--;
        adjacencies[a].push_back(b);
        adjacencies[b].push_back(a);
    }

    std::vector<int> dfs_stack;

    int first_uninit = 0;
    while (first_uninit < n_pupils)
    {
        init[first_uninit] = true;
        dfs_stack.push_back(first_uninit);
        while (!dfs_stack.empty())
        {
            int v = dfs_stack.back();
            dfs_stack.pop_back();
            if (discovered[v])
                continue;
            discovered[v] = true;
            bool team = teams[v];
            for (int adjacency : adjacencies[v])
            {
                if (init[adjacency] && teams[adjacency] == team)
                {
                    std::cout << "IMPOSSIBLE";
                    return 0;
                }
                dfs_stack.push_back(adjacency);
                init[adjacency] = true;
                teams[adjacency] = !team;
            }
        }
        while (init[first_uninit]) { first_uninit++; }
    }

    for (bool team : teams)
    {
        std::cout << (team ? "1" : "2") << " ";
    }

    return 0;
}

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