Building Teams

#include<bits/stdc++.h>
using namespace std;
bool bfs(int start, vector<vector<int>>& adj, vector<int>& team) {
    queue<int> q;
    q.push(start);
    team[start] = 1;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        int current_team = team[node];
        int next_team = (current_team == 1) ? 2 : 1;
        
        for (int neighbor : adj[node]) {
            if (team[neighbor] == 0) {
                team[neighbor] = next_team;
                q.push(neighbor);
            } else if (team[neighbor] == current_team) {
                return false;
            }
        }
    }
    return true;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<int> team(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) {
        if (team[i] == 0) {
            if (!bfs(i, adj, team)) {
                cout << "IMPOSSIBLE" <<"\n";
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << team[i] << " ";
    }
    cout<<"\n";
}

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