This page is still under construction.

Parts of this page are still being built. What you see may change.

Save Your Privacy!

Time limit8sMemory limit512 MB

Summary
Given which members each member knows and the set of leaked records, find the unique member whose knowledge could explain exactly that leak set, or -1.
Level

Medium6 of 10

Topics
Implementation, Brute force, Array, Math
Solved
No attempts yet

Problem

ICPC (International Committee of Privacy and Confidence) is an organization with many members around the world. As its name suggests, it is a group of secretive people who place great importance on privacy. Members may learn other members' personal information in the course of their work, but they are obligated to keep it strictly hidden.

Then one day, the personal information of several members leaked! As the ACM (Account Control Manager) of ICPC, you must promptly identify the members who leaked the information and deal with them severely.

You are an administrator with greater authority than the members, so you know completely who knows whose personal information. Of course, no member can leak the personal information of a member they do not know. However, the culprit need not have leaked all the personal information they know. From the list of members whose personal information leaked, determine (if possible) who leaked the personal information.

By the way, the purpose for which the organization ICPC operates is a top secret that even an administrator's authority cannot reveal.

Input

The input file contains multiple data sets. One data set is given in the following format.

N
M1 p1,1 p1,2... p1,M1
M2 p2,1 p2,2... p2,M2
:
MN pN,1 pN,2... pN,MN
K l1 l2... lK

N (2 ≤ N ≤ 100) is an integer representing the number of members. Each member is numbered from 1 to N. The following N lines give, in order of member number, the list of personal information that member knows. The first integer Mi (0 ≤ Mi ≤ N) on each line gives the number of integers that follow. The remaining integers are the numbers of the members whose personal information that member knows. The last line gives the list of members whose personal information leaked. K (1 ≤ K ≤ N) is the number of members whose information leaked, and the remaining integers are the numbers of those members.

You may assume the input is given correctly. That is, no member's list of known personal information contains the same member number twice or a nonexistent member number. The same holds for the list of members whose information leaked.

The input ends when N = 0.

Output

If you can identify the member who leaked the personal information, output that member's number. If you cannot, output -1.

There are two cases in which you cannot identify the leaker. One is when two or more members could have leaked the information. The other is when assuming any member leaked the information leads to a contradiction. In either case, your program must output -1.

Examples1

  1. Example 1

    Input
    3
    2 2 3
    1 1
    1 1
    2 2 3
    3
    2 2 3
    1 3
    1 2
    1 2
    5
    3 1 3 4
    4 1 3 4 5
    2 1 3
    2 1 2
    0
    3 1 3 5
    3
    2 2 1
    1 1
    1 2
    3 3 2 1
    0
    
    Expected output
    1
    -1
    2
    -1