Two Rounds

#include <algorithm>
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

bool GB(ll m, ll x)
{
    return ((m) & (1LL << (x)));
}

void SB(ll &m, ll x)
{
    m = ((m) | (1LL <<(x)));
}

vector <int> a, b;
vector <string> aa, bb; ///Bitmasks correspondientes con a y b
int f, tam;
long long solSet; ///Bitmask solucion
int sola, solb;

void solve(int i, long long s, int sa, int sb)
{
    if(i >= tam)
    {
        ///Ver si los puedo acomodar bien

        if(sola == -1)
        {
            if(sa > sb)
                swap(sa, sb);

            if(sa == sb && f%2 == 0)
                solSet = s, sola = sa, solb = sb;

            if((f - sb + sa) >= 0 && (f - sb + sa)%2 == 0)
                solSet = s, sola = sa, solb = sb;
        }
        return;
    }

    solve(i+1, s, sa+a[i], sb+b[i]);
    SB(s, i);
    solve(i+1, s, sa+b[i], sb+a[i]);
}

struct Grafo
{
    vector <vector <int> > Adj;
    vector <bool> u, color;

    bool bipartible;
    int c[2];

    string setA, setB;

    void dfs(int n)
    {
        if(color[n])
            setA[n] = '1';//SB(setA, n);
        else
            setB[n] = '1';//SB(setB, n);

        c[color[n]]++;
        u[n] = true;
        for(int i=0; i<Adj[n].size(); i++)
        {
            if(u[Adj[n][i]] && color[n] == color[Adj[n][i]])
                bipartible = false;
            else if(!u[Adj[n][i]])
            {
                color[Adj[n][i]] = 1-color[n];
                dfs(Adj[n][i]);
            }
        }
    }

    void leer()
    {
        int n, m, x,y;
        cin >> n >> m;

        n *= 2;

        Adj = vector <vector <int> > (n+1, vector <int> ());
        u = vector <bool> (n+1, false);
        color = vector <bool> (n+1, false);

        bipartible = true;

        for(int i=0; i<m; i++)
        {
            cin >> x >> y;
            Adj[x].push_back(y);
            Adj[y].push_back(x);
        }

        string patron(102, '0');
        for(int i=1; i<n+1; i++)
            if(Adj[i].size() && !u[i])
            {
                color[i] = 0;
                c[0] = 0, c[1] = 0;

                setA = patron, setB = patron;
                dfs(i);

                a.push_back(c[0]);
                b.push_back(c[1]);

                aa.push_back(setA);
                bb.push_back(setB);
            }
        if(!bipartible)
        {
            cout << "IMPOSSIBLE" << endl;
            return;
        }
        f = 0;

        ///Ver cuántos nodos están sin conflictos

        vector <int> sobra;

        for(int i=1; i<=n; i++)
            if(Adj[i].size() == 0)
                sobra.push_back(i), f++;

        sola = -1, solb = -1;
        tam = a.size();
        solve(0, 0, 0, 0);

        if(sola == -1)
        {
            cout << "IMPOSSIBLE" << endl;
            return;
        }

        vector <int> ra, rb;

        for(int i=0; i<tam; i++)
        {
            bool z = GB(solSet, i);
            if(z == 0) ///Queda como está
            {
                for(int j=0; j<101; j++)
                    if(aa[i][j] == '1')
                        ra.push_back(j);
                for(int j=0; j<101; j++)
                    if(bb[i][j] == '1')
                        rb.push_back(j);
            }
            else
            {
                for(int j=0; j<101; j++)
                    if(aa[i][j] == '1')
                        rb.push_back(j);
                for(int j=0; j<101; j++)
                    if(bb[i][j] == '1')
                        ra.push_back(j);
            }
        }

        ///Ahora tengo que dividir los problemas que son neutros

        for(int i=0; i<sobra.size(); i++)
        {
            if(ra.size() < rb.size())
                ra.push_back(sobra[i]);
            else
                rb.push_back(sobra[i]);
        }

        for(int i=0; i<rb.size(); i++)
            cout << rb[i] << " ";
        cout << endl;

        for(int i=0; i<ra.size(); i++)
            cout << ra[i] << " ";
        cout << endl;
    }
};

int main()
{
    ///Mi código es un asco
    ///Pobre de vos si venís a ver
    ///cómo se resuelve este problema
    ///Jajaja
    Grafo g;
    g.leer();

    return 0;
}