Building Teams

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; ++i)
#define BR "\n"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> pi;

bool dfs(int s, vi adj[], bool vis[], int color[], int nxtcolor) {
  if (vis[s]) {
    if (color[s] != nxtcolor)
      return false;
    else
      return true;
  }
  vis[s] = true;
  // process s
  // color s
  color[s] = nxtcolor;
  for (auto u : adj[s]) {
    if (!dfs(u, adj, vis, color, nxtcolor == 1 ? 2 : 1)) {
      return false;
    }
  }
  return true;
}

int main() {
  // uncomment if io is a bottleneck
  // ios::sync_with_stdio(0);
  // cin.tie(0);

  // uncomment to read cin from a file
  // freopen("a.txt", "r", stdin);
  int n, m;
  cin >> n >> m;

  vi friends[n + 1];
  REP(i, 0, m) {
    int a, b;
    cin >> a >> b;
    friends[a].PB(b);
    friends[b].PB(a);
  }

  int color[n + 1] = {};

  bool vis[n + 1] = {};
  bool imp = false;
  REP(i, 1, n + 1) {
    if (vis[i]) continue;
    if (!dfs(i, friends, vis, color, 1)) {
      imp = true;
    }
  }

  if (imp) {
    cout << "IMPOSSIBLE" << BR;
  } else {
    REP(i, 1, n) { cout << color[i] << " "; }
    cout << color[n] << BR;
  }

  return EXIT_SUCCESS;
}

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