2767. Letter Lies

单点时限: 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:

  • Some sentences are greetings and can appear only at the beginning of the letter. Each letter has to start with a greeting.
  • Some sentences are closings and can appear only at the end. Each letter has to end with a closing.
  • No sentence can appear twice in the same letter.
  • Successor rules: Each sentence restricts the list of other sentences that can follow. For example, a sentence saying “Hello” cannot be followed by “This concludes our offer”.
  • The resulting letter must have an appropriate length. Therefore, the exact number of sentences is specified.

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
2 1000000 1 1
1 1 2
2 0
0 0 0 0

2 人解决,3 人已尝试。

2 份提交通过,共有 11 份提交。

8.9 EMB 奖励。

创建: 12 年,1 月前.

修改: 4 年,3 月前.

最后提交: 11 年,1 月前.

来源: CTU Open Contest 2009