AIOC Banner

Problem: Bureaucratic Bungling

Want to try solving this problem? You can submit your code online if you log in or register.

Bureaucratic Bungling

Input File: bungin.txt
Output File: bungout.txt
Time Limit: 0.3 seconds

Once more it's enrolment time at the university. With great caution you fill out your enrolment form (labelled 21-B), double check it and then stride confidently into the administration building.

"Form 21-B?" asks the administrator smiling sweetly. "Why I'm sorry dear, you can't enrol without form 47-H. But since you have form 21-B, I can give you form 11-A. Here you are. Next please!"

With a sigh you stroll up to the Registrar's Office. They take a glance at your 11-A and explain sadly that it's not enough to give you form 47-H but it's enough for them to give you form 6-F. Shoulders slumped and 6-F in hand, you head across to the mathematics office. It's going to be a long day.

Your task in this problem is to negotiate your way through this bureaucratic paper maze. There are N different types of form at the university which we will label 1,2,3,...,N for simplicity. There are A different administrators whom we will label 1,2,3,...,A, each of whom carries out a particular task. Each task involves checking that the student (yourself) is carrying a particular set of forms, and if so then giving the student a new set of forms.

You are told which form(s) you begin with and which form you are aiming to collect. You must write a program that finds the smallest number of administrators that you must visit in order to collect this final form.

Note that an administrator will never take forms away from you; you simply collect more and more forms until your goal is achieved. You may assume that it is always possible to achieve your goal.


The first line of input will contain the single integer N (1 <= N <= 10) representing the number of different types of form.

The second line of input will contain a list of the forms that you begin with (represented as integers between 1 and N inclusive) followed by the integer 0. These integers will all be separated by spaces. No form will appear more than once in this list.

The third line will contain the single integer representing the final form that you are aiming to collect.

The fourth line will contain the single integer A (1 <= A <= 60,000) representing the number of administrators.

The following A lines will describe administrators 1,2,3,...,A (one line per administrator). Each such line begins with the list of the forms that the administrator requires, followed by a 0, then the list of the additional forms that they will give you, followed by another 0. These integers will all be separated by spaces and no form will appear more than once on each line.


Output should consist of the list of administrators that you visit (represented as integers between 1 and A inclusive), one administrator per line. Administrators should be listed in the order in which you visit them.

Sample Input

1 3 0
1 5 0 4 0
1 0 3 5 0
3 4 0 2 0
1 3 0 4 5 0

In this example there are five types of form. You begin with forms 1 and 3 and your goal is to collect form 2. There are four administrators.

Sample Output


If you present forms 1 and 3 to the fourth administrator, you will receive forms 4 and 5. Now you can present forms 3 and 4 to the third administrator and receive form 2 which fulfils your goal.


The score for each input file will be calculated as follows. Say the smallest number of visits required is S. If the output file does not contain a valid procedure for obtaining the final form, the score will be 0%. If the output file does contain a valid procedure using V visits, the score will be:


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 24 March 2023,  8:25pm AEDT