Return to Base

You are given \(n\) regions numbered \(1,2,\dots,n\). Regions \(1\) through \(b\) are bases.

For each region \(i\) (\(1 \le i \le n\)), you are given a nonempty set \(A_i\) of destination regions. There are \(r\) robots, where the \(i\)th robot starts at region \(s_i\). You can issue a move command any number of times. When you issue a move command, if a robot is currently at region \(i\) then it independently and uniformly randomly moves to some region in \(A_i\).

Your task is to determine whether there exists a nonnegative integer \(k\) such that after issuing exactly \(k\) move commands, each robot is guaranteed to be at a base (i.e. in one of the regions \(1,2,\dots,b\)), regardless of the random choices. If such a \(k\) exists, output any one of them; otherwise, output \(-1\).

Note: When \(k=0\), the robots do not move, so the condition holds if and only if every robot starts in a base. For \(k \ge 1\), the condition means that for every robot starting at region \(i\), every possible sequence of \(k\) transitions (using the sets \(A_i\)) leads to a region \(\le b\). In other words, for every region \(i\) reached within these \(k\) moves, if a move is issued further then its destination must always be among the bases. This forces a closure condition: if any reachable region \(v\) has an element in \(A_v\) that is not a base, then for any \(k \ge 1\) the guarantee fails for some robot starting from some region. It can be shown that if a valid \(k\) exists then one of \(0\) or \(1\) is a valid answer.

inputFormat

The first line contains three integers \(n, b, r\) \(\;(1 \le b \le n)\). Then follow \(n\) lines describing the sets \(A_1, A_2, \dots, A_n\). The \(i\)th of these lines begins with an integer \(c_i\) (the size of \(A_i\)), followed by \(c_i\) integers representing the elements of \(A_i\). Finally, the last line contains \(r\) integers \(s_1, s_2, \dots, s_r\) representing the initial positions of the robots.

outputFormat

Output a single integer: an arbitrary \(k\) (with \(0 \le k < 10^{200}\)) such that after issuing exactly \(k\) move commands, every robot is guaranteed to be at a base, or output \(-1\) if no such \(k\) exists.

sample

3 2 2
2 1 2
1 2
1 3
1 2

0