CFR 688 C. NP-Hard Problem ( Bipartite Coloring )

Problem - C - Codeforces
It's not difficult to see that only a bipartite graph will meet the requirements.

bool dfs( int u, const vvi &G, vi &col ){
    for( int v : G[ u ] ){
        if( col[ v ] && col[ u ] == col[ v ] ) return false;
        if( !col[ v ] ){
            col[ v ] = 3 - col[ u ];
            if( !dfs( v, G, col ) ) return false;
        }
    }
    return true;
}

void solve(){
    int N, M; cin >> N >> M;
    vvi G( N );
    for( int i = 0; i < M; ++i ){
        int u, v; cin >> u >> v;
        --u, --v;
        G[ u ].push_back( v );
        G[ v ].push_back( u );
    }
    vi col( N );
    for( int u = 0; u < N; ++u )
        if( !col[ u ] ){
            col[ u ] = 1;
            if( !dfs( u, G, col ) ){
                cout << "-1\n";
                return;
            }
        }
    vi ans;
    for( int u = 0; u < N; ++u )
        if( col[ u ] == 1 )
            ans.push_back( u + 1 );
    cout << ans.size() << "\n";
    for( int i = 0; i < ans.size(); ++i )
        cout << ans[ i ] << ( i + 1 == ans.size() ? '\n' : ' ' );
    ans.clear();
    for( int u = 0; u < N; ++u )
        if( col[ u ] == 2 )
            ans.push_back( u + 1 );
    cout << ans.size() << "\n";
    for( int i = 0; i < ans.size(); ++i )
        cout << ans[ i ] << ( i + 1 == ans.size() ? '\n' : ' ' );
}