BuildingTeams.cpp

#include <bits/stdc++.h>
using namespace std;
int N = 1e5 + 2;
vector<vector<int>>adj(N);
vector<bool>check(N,false);
vector<int>ans(N);
vector<int>dist(N);
int oho = 0;
 
void BFS(int i){
    queue<int>curr;
    curr.push(i);
    dist[i] = 0;
 
    while(curr.front()){
        i = curr.front();
        curr.pop();
        if(dist[i]%2){ans[i] = 2;}
        else{ans[i] = 1;}
 
        check[i] = true;
 
        for(int j : adj[i]){
            if(ans[i] == ans[j]){oho = 1;return;}
            if(check[j])continue;
            curr.push(j);
            dist[j] = dist[i] + 1 ;
        }
 
    }
}
 
int main(){
    int n,m;
    cin >> n >> m;
 
    while(m--){
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
 
    for(int i = 1 ; i <= n && !oho; i ++){
        if(check[i])continue;
        BFS(i);
    }
 
    if(oho){cout <<"IMPOSSIBLE";return 0;}
 
    for(int i = 1 ; i <= n ; i ++)
    cout << ans[i] << " ";
    return 0;
}