Building Teams

#include <bits/stdc++.h>
using namespace std;

int main () {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> fs(n+1);
    for(int i=0; i < m; i++) {
        int l, r; cin >> l >> r;
        fs[l].push_back(r);
        fs[r].push_back(l);
    }

    vector<uint8_t> v(n+1);
    vector<int> dj;

    stack<int> st;
    for(int i=1; i <= n; i++) {
        st.push(i);
        while(!st.empty()){
            int c = st.top(); st.pop();
            if(!v[c]) {
                v[c]=1;
                if(i == c) dj.push_back(c);
                for(int n : fs[c]) st.push(n);
            }
        }
    }
    std::fill(v.begin(), v.end(), 0);
    // cycle?
    int depth = 0;
    for(int d : dj) {
        st.push(d);
        while(!st.empty()){
            int cse = depth % 2 ? 1 : 2;
            int c = st.top(); st.pop();
            if(v[c] == 0) {
                v[c]=cse;
                for(int n : fs[c]) st.push(n);
            }
            else if (v[c] != cse) {
                cout << "IMPOSSIBLE\n";
                return 0; 
            }
            depth++;
        }
    }

    cout << (int)v[1];
    for(int i = 2; i <= n; i++)
        cout << ' ' << (int)v[i];
    cout << '\n';

    return 0;
}

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