2 人解决，3 人已尝试。
2 份提交通过，共有 11 份提交。
8.9 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
Some government projects are not done by government offices themselves, but are instead contracted to private companies. The selection of the best candidate is a task for a specially selected experts. Before the selection process starts, all the candidates send letters with their offer. The committee then picks the best offer based on its price and quality.
That was the theory. . . In reality, the selection process is often just a formality and the winner was chosen long before, based on the bribe given to the committee. To masquerade these frauds, fake candidate companies are included in the process. And, of course, it is necessary to pretend that the offer letters by these companies have been received. Some people are involved in such selection procedures so often that they implemented an automated letter generator to make their work easier. The generator can assemble letters from a list of pre-defined sentences and the following rules:
Would you help ACM to detect fake letters generated by this program? You are given a set of letter-generator rules and your task is to compute the total number of different valid letters that can be assembled.
The input will consist of several test scenarios. Each scenario starts by a line with four positive integers N, L, B, F. N is the number of all sentences (1 ≤ N ≤ 1000), B and F are the number of greetings and closings (1 ≤ B,F ≤ 1000), and L is the desired length (1 ≤ L ≤ 1000000).
Then there are N lines with successor rules; i-th of them is composed of the number i, integer Di (0 ≤ Di ≤ 1000), and a list of Di integers determining the sentences that can follow sentence number i.
Next B lines contain numbers of all possible starting sentences and the last F lines numbers of all possible final sentences.
The last scenario is followed by a line containing four zeros.
The author of the generator did not implement any check that some sentence occurs more than once. Instead, this is always guaranteed by the set of successor rules. If these rules are followed, you may safely assume that no letter can ever contain the same sentence twice, that a greeting can appear only at the beginning and a closing only at the end of the letter.
For each scenario, output a line with one integer number ― the total number of valid letters with exactly L sentences. Please note that this number may exceed 232. If there is no valid letter of the given length, output the string “impossible”.
4 2 2 2 1 1 3 2 1 4 3 0 4 0 1 2 4 3 2 1000000 1 1 1 1 2 2 0 1 2 0 0 0 0
2 impossible
2 人解决，3 人已尝试。
2 份提交通过，共有 11 份提交。
8.9 EMB 奖励。