Building Teams

#include <vector>
struct UnionFind {
  std::vector<int> sets;
  int numSepSets;
  //sets[i] = x: if x<0, i is a root, and -x is the size else i is a child of parent x.
  UnionFind(int n) : sets(n, -1), numSepSets(n) {}
  bool sameRoot(int a, int b) { return find(a) == find(b); }
  int sizeOfSet(int x) { return -sets[find(x)]; }

  //Path compression
  int find(int x) 
  { 
    return sets[x] < 0 ? x : sets[x] = find(sets[x]); 
  }

  //Union by rank
  bool unionOf(int a, int b) 
  {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (sets[a] > sets[b]) std::swap(a, b); // or if (-sets[a] < -sets[b]) std::swap(a, b);
    sets[a] += sets[b]; 
    sets[b] = a;
    --numSepSets;
    return true;
  }
};


#include <iostream>
int main(){
  int n,m;
  std::cin >> n >> m;
  UnionFind dsu(n + 2);
  for (int f = 0; f<m; ++f){
    int p1, p2;
    std::cin >> p1 >> p2;
    if ((dsu.sameRoot(p1-1, n) && !dsu.sameRoot(p2-1, n+1))){
      dsu.unionOf(p2-1, n+1);
    } else if ((dsu.sameRoot(p1-1, n+1) && !dsu.sameRoot(p2-1, n))){
      dsu.unionOf(p2-1, n);
    } else if ((!dsu.sameRoot(p1-1, n) && dsu.sameRoot(p2-1, n+1))){
      dsu.unionOf(p1-1, n);
    } else if ((!dsu.sameRoot(p1-1, n+1) && dsu.sameRoot(p2-1, n))){
      dsu.unionOf(p1-1, n+1);
    } else if (dsu.sameRoot(p1-1, p2-1)){
      std::cout << "IMPOSSIBLE" << "\n";
      return 0;
    }else {
      dsu.unionOf(p1-1, n);
      dsu.unionOf(p2-1, n+1);
    }
  }
  
  bool possible = true;
  std::vector<int> groups(n);
  for (int p = 0; p<n; ++p){
    if (dsu.sameRoot(p, n) && dsu.sameRoot(p, n+1)){
      possible = false;
      break;
    } else if (dsu.sameRoot(p, n)){
      groups[p] = 1;
    } else if (dsu.sameRoot(p, n+1)){
      groups[p] = 2;
    } else {
      dsu.unionOf(p, n+1);
      groups[p] = 2;
    }
  }

  if (!possible){
    std::cout << "IMPOSSIBLE";
  }else{
    for (int p = 0; p<n; ++p){
      std::cout << groups[p] << " ";
    }
  }
  std::cout << std::endl;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED