#include #include #include using namespace std; int n, l, b, f; #define DEBUG(a) vector graf[2000]; struct V { int vrchol; int nasob; }; bool operator == (const V &a, const V &b) { return a.vrchol == b.vrchol; } bool operator < (const V &a, const V &b) { return a.vrchol < b.vrchol; } bool operator <= (const V &a, const V &b) { return a.vrchol <= b.vrchol; } int main() { scanf("%d %d %d %d\n",&n,&l,&b,&f); while (n >0 && l > 0 && b > 0 && f > 0) { for (int i = 1; i < n+1; i++) { graf[i].clear(); int cv, ps, vrch; scanf("%d %d", &cv, &ps); for (int j = 0; j < ps; j++) { scanf("%d", &vrch); graf[i].push_back(vrch); //printf("cesta z %d do %d\n", i, vrch); } } for (int i = 0; i < b; i++) { int start; scanf("%d", &start); graf[n+1].push_back(start); } for (int i = 0; i < f; i++) { int konec; scanf("%d", &konec); graf[konec].push_back(n+2); } // cool :-) if (l > n) printf("impossible\n"); else { // CVUTaci neumi nakonfigurit vim V pocatek; pocatek.vrchol = n+1; pocatek.nasob = 1; set vrstva; set nasled; vrstva.insert(pocatek); for (int i = 0; i < l+1; i++) { for (set::iterator it = vrstva.begin(); it != vrstva.end(); ++it) { for (vector::iterator it2 = graf[(*it).vrchol].begin(); it2 != graf[(*it).vrchol].end(); ++it2) { V vyhledavatko; vyhledavatko.vrchol = (*it2); set::iterator f = nasled.find(vyhledavatko); if (f == nasled.end()) { V novy; novy.vrchol = (*it2); novy.nasob = (*it).nasob; nasled.insert(novy); } else { V tmp = (*f); nasled.erase(f); tmp.nasob += (*it).nasob; nasled.insert(tmp); } } } vrstva = nasled; nasled.clear(); DEBUG( printf("vrstva %d: \n", i); for (set::iterator it = vrstva.begin(); it != vrstva.end(); ++it) { printf(" %d (%d)\n", (*it).vrchol, (*it).nasob); } ) } V koncovych; koncovych.vrchol = n+2; set::iterator f = vrstva.find(koncovych); int vysledek = 0; if (f != vrstva.end()) vysledek = (*f).nasob; if (vysledek == 0) printf("impossible\n"); else printf("%d\n", vysledek); } scanf("%d %d %d %d\n",&n,&l,&b,&f); } return 0; }