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){
    std::pair<int, int> p;
    std::cin >> p.first >> p.second;
    dsu.unionOf(p.first-1, n);
    dsu.unionOf(p.second-1, n+1);
  }
  if (dsu.sameRoot(n, n+1)){
    std::cout << "IMPOSSIBLE" << "\n";
  }

  for (int p = 0; p<n; ++p){
    if (dsu.sameRoot(p, n)){
      std::cout << 1 << " ";
    } else if (dsu.sameRoot(p, n+1)){
      std::cout << 2 << " ";
    } else {
      std::cout << 2 << " ";
    }
  }
  std::cout << "\n";
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER