ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2004

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Bureaucracy

Time limit: 1.0 second
Memory limit: 64 MB
After the wonderful properties of the Field of Wonder in the Fools Country were discovered, the huge bureaucratic mechanism appeared. So, to plant his coin in the field, Pinocchio has to gather a lot of documents. Moreover it is impossible to get some documents without getting some set of another documents first.
The issue of one type of documents is a prerogative of exactly one bureaucrat. And all of these bureaucrats are so lazy, that they agree to work only one day a week. So there are incredibly long queues to the bureaucrat’s offices during the visiting days and it really takes a whole day to get only one document.
Pinocchio wants to realize a profit on his investments as soon as possible. The only way to do it is to gather all necessary documents as soon as possible. He found out what bureaucrats he needs to visit and numbered them from 1 to N inclusive. He found out the visiting day of week and the set of documents he should have on his hands during the visit for each of the bureaucrat.
After a short time of thinking, Pinocchio understood that he can’t find the optimal solution of his problem. And then he promised to pay a half of his future profits to one, who will help him.


The first line of input contains amount of bureaucrats in the Fools Country N (1 ≤ N ≤ 100) and amount of days in a week according to calendar of Fools Country L (1 ≤ L ≤ 100). The next line contains the numbers of bureaucrat’s visiting days Ai (1 ≤ AiL). The next N lines describe the sets of documents, necessary for receiving the corresponding document. Set of documents consists of numbers delimited by spaces. It is known, that ith line doesn’t contain document with number i. Each line is ended by 0 which means the end of the set. If the set is empty (line contains single 0), the document can be gathered without any other documents. After these lines there is one more number — current day of week K (1 ≤ KL). The next line contains the list of documents Pinocchio already has. This list consists of numbers delimited by spaces and it ends with 0. And the last line of input contains the list of documents necessary for Pinocchio in the same format.
Though the Fools Country seems to have an ideal income source but because of the official circumlocution the state can’t get a huge part of the taxes. As a result there is enough money to keep only one office. So there may work not more than one official at the same time.


If it is impossible to get the necessary set of documents then output "No Solution". Otherwise it should output the minimal amount of days (excluding the current day) he will spend gathering the necessary set of documents, and in the next line it should output all gathered documents delimited by spaces in chronological order. If there are several such answers then the program may output any of them.


2 7
1 2
1 0
1 0
2 0
Problem Author: Anatoly Uglov, Evgeny Krokhalev
Problem Source: The 10th Collegiate Programming Contest of the High School Pupils of the Sverdlovsk Region (October 16, 2004)
To submit the solution for this problem go to the Problem set: 1337. Bureaucracy