here is code, it use O(nlogn)
if problem has O(n) algo,please write your code.
sorry for my bad english.


#include <iostream>
#include <set>
#include <vector>

using namespace std;

const int MAXN= 7163+ 5;

bool group[MAXN];
int n, Size[2];
int d[MAXN];
vector <int> adj[MAXN];

struct node{
    int num;

    node (int _num= -1) : num(_num) {}

    inline bool operator < (const node &second) const{
        if (d[second.num]!= d[num])
            return d[num] > d[second.num];
        return num > second.num;
    }
};
set <node> sit;
/***********************************************************/
inline void partition (){
    while (true){
        node v= *sit.begin();
        if (d[v.num] < 2)
            return;
        for (int i= 0;i< (int)adj[v.num].size();i ++){
            int tmp= adj[v.num][i];
            node k(tmp);
            if (group[tmp]== group[v.num]){
                sit.erase (tmp);
                d[tmp] --;
                sit.insert (tmp);
            }
            else{
                sit.erase (tmp);
                d[tmp] ++;
                sit.insert (tmp);
            }
        }
        Size[group[v.num]] --;
        group[v.num]= !group[v.num];
        Size[group[v.num]] ++;
        sit.erase (v);
        d[v.num]= adj[v.num].size()- d[v.num];
        sit.insert (v);
    }
}
/*********************************************/
int main (){
    scanf ("%d", &n);
    for (int i= 1;i<= n;i ++){
        scanf ("%d", &d[i]);
        for (int j= 1;j<= d[i];j ++){
            int tmp;
            scanf ("%d", &tmp);
            adj[i].push_back (tmp);
        }
        group[i]= false;
        node tmp (i);
        sit.insert (tmp);
        Size[0] ++;
    }
    partition ();
    int cur= 0;
    if (Size[0] < Size[1])
        cur= 0;
    else if (Size[1] < Size[0])
        cur= 1;
    else
        cur= group[1];
    printf ("%d\n", min (Size[0], Size[1]));
    for (int i= 1;i<= n;i ++)
        if (group[i]== cur)
            printf ("%d ", i);

    return 0;
}

I used only BFS