A pitch-black room

When I woke up, Mr. A was in a pitch-black room. Apparently, Mr. A got lost in a dungeon consisting of N rooms. You couldn't know which room A got lost in, but fortunately he got a map of the dungeon. Let's show A the way to go and lead to a bright room.

It is known that M of the N rooms are pitch black, and the D_1, D_2, ..., and D_Mth rooms are pitch black, respectively. Also, there are exactly K one-way streets from all the rooms in order, and the roads from the i-th room are v_ {i, 1}, v_ {i, 2}, ..., v_ {i, respectively. , K} Connected to the third room. You can follow the a_1, a_2, ..., a_lth roads in order from the room you are in for Mr. A. However, when Mr. A reaches the bright room, he ignores the subsequent instructions. You cannot know the information of the room where Mr. A is currently before and after the instruction, so you must give the instruction sequence so that you can reach the bright room no matter which room you are in. Answer the length of the shortest of such instructions.

Constraints

* 2 ≤ N ≤ 100
* 1 ≤ M ≤ min (16, N − 1)
* 1 ≤ K ≤ N
* 1 ≤ D_i ≤ N
* D_i are all different
* 1 ≤ v_ {i, j} ≤ N
* All dark rooms can reach at least one bright room



Input Format

Input is given from standard input in the following format.


NMK
D_1 D_2 ... D_M
v_ {1,1} v_ {1,2} ... v_ {1,K}
v_ {2,1} v_ {2,2} ... v_ {2, K}
...
v_ {N, 1} v_ {N, 2} ... v_ {N, K}


Output Format

Print the answer in one line.

Sample Input 1


4 2 2
1 2
twenty four
3 1
4 2
13


Sample Output 1


2


<image>
If you give the instruction 1, 1

* If A's initial position is room 1, the second move will reach room 3.
* If A's initial position is room 2, the first move will reach room 3.



Sample Input 2


3 2 2
1 2
twenty three
1 2
twenty one


Sample Output 2


3


<image>
If you give instructions 2, 1, 2

* If A's initial position is room 1, the first move will reach room 3.
* If A's initial position is room 2, the third move will reach room 3.



Sample Input 3


6 3 3
one two Three
4 1 1
2 5 2
3 3 6
4 4 4
5 5 5
6 6 6


Sample Output 3


3


<image>
Beware of unconnected cases and cases with self-edges and multiple edges.





Example

Input

4 2 2
1 2
2 4
3 1
4 2
1 3


Output

2

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(0, -1), (1, 0), (0, 1), (-1, 0)]
ddn = [(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, m, k) = LI()
	d = LI_()
	v = [LI_() for _ in range(n)]
	dd = collections.defaultdict(lambda : None)
	for i in range(m):
		dd[d[i]] = i
	ii = [2 ** _ for _ in range(m)]
	vv = [[ii[dd[v[c][i]]] if not dd[v[c][i]] is None else 0 for c in d] for i in range(k)]
	m2 = 2 ** m
	u = [None] * m2
	u[-1] = 1
	q = [m2 - 1]
	r = 0
	while q:
		r += 1
		nq = []
		for qd in q:
			qdi = [di for di in range(m) if qd & ii[di]]
			for vi in range(k):
				t = 0
				vvi = vv[vi]
				for di in qdi:
					t |= vvi[di]
				if not u[t] is None:
					continue
				if t == 0:
					return r
				u[t] = 1
				nq.append(t)
		q = nq
	return -1
print(main())


import sys
from collections import defaultdict

def main():
	input = sys.stdin.readline
	(n, m, k) = map(int, input().split())
	d = list(map(int, input().split()))
	l = [-1] * n
	for i in range(m):
		l[d[i] - 1] = i
	A = [list(map(int, input().split())) for _ in range(n)]
	a = [[l[A[i - 1][j] - 1] if l[A[i - 1][j] - 1] != -1 else None for i in d] for j in range(k)]
	c = [-1] * (1 << m)
	c[(1 << m) - 1] = 0
	D = [1 << i for i in range(m + 1)]
	x = [-1] * m
	q = defaultdict(int)
	Range = range(m)
	K = 0
	q[0] = -1
	R = 1
	while 1:
		mask = q[K]
		K += 1
		score = c[mask] + 1
		x = [i for i in Range if mask & D[i]]
		for ai in a:
			tmp = 0
			for j in x:
				aji = ai[j]
				if aji != None:
					tmp |= D[aji]
			if c[tmp] == -1:
				c[tmp] = score
				q[R] = tmp
				R += 1
				if tmp == 0:
					print(score)
					return
main()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(0, -1), (1, 0), (0, 1), (-1, 0)]
ddn = [(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, m, k) = LI()
	d = LI_()
	v = [LI_() for _ in range(n)]
	dd = collections.defaultdict(lambda : None)
	for i in range(m):
		dd[d[i]] = i
	vv = []
	for c in d:
		vv.append([dd[v[c][i]] for i in range(k)])
	vvv = [[vv[i][j] for i in range(m)] for j in range(k)]
	u = set()
	m2 = 2 ** m
	u.add(m2 - 1)
	q = [(m2 - 1, 1)]
	ii = [2 ** _ for _ in range(m)]
	while q:
		(qd, qk) = q.pop(0)
		qdi = [di for di in range(m) if qd & ii[di]]
		for vi in range(k):
			t = 0
			vvi = vvv[vi]
			for di in qdi:
				if not vvi[di] is None:
					t |= ii[vvi[di]]
			if t in u:
				continue
			if t == 0:
				return qk
			u.add(t)
			q.append((t, qk + 1))
	return -1
print(main())