Building Teams

#include <bits/stdc++.h>
using namespace std;

bool dfs(int s, int g, vector<vector<int>> &adj, vector<int> &gr) {
    gr[s] = g;

    for (auto &u : adj[s]) {
        if (gr[u] == -1) {
            int ng = (g == 1) ? 2 : 1;
            bool res = dfs(u, ng, adj, gr);
            if (res == false) {
                return false;
            }
        } else if (gr[u] == g) {
            return false;
        }
    }
    return true;
}

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

    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> gr(n + 1, -1);

    bool pos = true;
    for (int i = 1; i <= n; i++) {
        if (gr[i] == -1) {
            if (!dfs(i, 1, adj, gr)) {
                pos = false;
                break;
            }
        }
    }
    if (!pos) {
        cout << "IMPOSSIBLE" << "\n";
    } else {
        for (int j = 1; j <= n; j++) { // what
            cout << gr[j] << " ";
        }
        cout << "\n";
    }
}

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