1 // File Name: hust1017.cpp  2 // Author: darkdream  3 // Created Time: 2014年10月04日 星期六 16时47分57秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 const int maxnode = 100010; 26 const int MaxM = 1010; 27 const int MaxN = 1010; 28 using namespace std; 29 struct DLX 30 { 31     int n ,m ,size; 32     int L[maxnode],R[maxnode],U[maxnode],D[maxnode],Row[maxnode],Col[maxnode]; 33     int ansd,ans[MaxN]; 34     int H[MaxN],S[MaxM]; 35     void init(int _n,int _m) 36     { 37         n = _n; 38         m = _m; 39         for(int i = 0;i <= m;i++) 40         { 41             S[i] = 0; // S 代表的是每一列的颜色 42             U[i] = D[i] = i; 43             L[i] = i-1; 44             R[i] = i+1; 45         } 46         R[m] = 0; L[0] = m; 47         size = m; 48         for(int i = 1;i <= n;i++) 49             H[i] = -1;  //  H[i]  代表第I 行的头 50     } 51     void Link(int r,int c) 52     { 53         ++S[Col[++size]=c]; 54         Row[size] = r; 55         D[size] = D[c]; 56         U[D[c]] = size; 57         U[size] = c; 58         D[c] = size; 59         if(H[r] < 0)H[r] = L[size] = R[size] = size; 60         else 61         { 62             R[size] = R[H[r]]; 63             L[R[H[r]]] = size; 64             L[size] = H[r]; 65             R[H[r]] = size; // 插入到  H[r] 的右边 66         } 67     } 68     void remove(int c) //列为单位，横向 69     { 70         L[R[c]] = L[c]; R[L[c]] = R[c]; 71         for(int i = D[c];i != c;i = D[i]) 72             for(int j = R[i];j != i;j = R[j]) 73             { 74                 U[D[j]] = U[j]; 75                 D[U[j]] = D[j]; 76                 --S[Col[j]]; 77             }//删除一列，k行 78     } 79     void resume(int c) 80     { 81         L[R[c]] = R[L[c]] = c; 82         for(int i = U[c];i != c; i = U[i]) 83             for(int j = L[i];j != i ;j = L[j]) 84             { 85                  U[D[j]] = j; 86                  D[U[j]] = j; 87                  ++S[Col[j]]; 88             } 89     } 90     bool Dance(int d) 91     { 92        if(R[0] == 0 ) 93        { 94           ansd = d; //答案长度 95           return true; 96        } 97        int c = R[0]; 98        for(int i = R[c];i != 0 ;i = R[i]) 99            if(S[i] < S[c])100                 c = i ; 101        remove(c);102        for(int i = D[c]; i != c;i = D[i])103        {104            ans[d] = Row[i];105            for(int j = R[i]; j != i ;j = R[j])  remove(Col[j]);106            if(Dance(d+1)) return true;107            for(int j = L[i]; j != i ;j = L[j])  resume(Col[j]);108        }109        resume(c);110        return false;111     }112 };113 114 DLX g;115 int main(){116    int n , m ; 117    while(scanf("%d %d",&n,&m) != EOF)118    {119       g.init(n,m);120       int num, j; 121       for(int i = 1;i <= n;i ++)122       {123         scanf("%d",&num);124         while(num--)125         {126           scanf("%d",&j);127           g.Link(i,j);128         }129       }130       if(!g.Dance(0)) printf("NO\n");131       else{132         printf("%d ",g.ansd);133         for(int i = 0;i < g.ansd;i ++)134           printf(" %d",g.ans[i]);135         printf("\n"); 136       }137       138    }139 return 0;140 }