Document Compression |
Alice needs to send text documents to Bob using the Internet. They want to use the communication channel as efficiently as possible, thus they decided to use a document codification scheme based on a set of basis documents. The scheme works as follows:
For example, suppose that the basis document set contains the following documents, each one specified by the list of different terms that it contains:
Document 1: {2, 5, 7, 10}
Document 2: {8, 9, 10}
Document 3: {1, 2, 3, 4}
Now, suppose that Alice wants to transmit the document {1, 2, 3, 4, 5, 7, 10}. This document can be obtained by combining
the basis documents 1 and 3, so Alice transmits this list of two indices and Bob uses it to rebuild the original document.
Your work is, given a set of basis documents and a document to be transmitted, to find the minimum number of basis
documents needed to represent it, if it can be represented; otherwise, you have to indicate that it is impossible to attain a
representation.
Each test case is described as follows:
The last test case is followed by a line containing two zeros.
For each test case you must print a line containing the integers r1, r2,..., rN (with a blank between each two numbers), where ri is the minimum number of basis documents required to represent the i-th document of the input ( 1 i N). If it is impossible to represent the i-th document, then ri must be the number `0'.
3 1 4 2 5 7 10 3 8 9 10 4 1 2 3 4 7 1 2 3 4 5 7 10 2 3 2 2 1 2 4 3 2 3 4 3 3 1 2 4 3 1 4 2 0 0
2 1 0 2