问题陈述
我醒来时,A在一个漆黑的房间里。 显然,你 看来我误入了一个由[ N 房间组成的地牢。 你不知道自己进入了哪个房间,但幸运的是,你设法弄到了一张地下城地图。 让我们为你展示应该走的道路,带你进入一个明亮的房间。
N 在一个单人间 M 每个房间都漆黑一片,而且 众所周知, D_1, D_2, ..., D_M 房间完全黑暗。 另外,每个房间, K 书的两面道路都按顺序排列,i 从房间出去的路径是 它与 v_{i,1}, v_{i,2}, ..., v_{i,K} 房间相连。 你来自你现在所在的这个房间, a_1, a_2, ..., a_l 可以让第...号的道路按顺序前进。 但是,如果A君到达明亮的房间,他之后的指示将被忽视。 由于你无法在指示转达时知道A君所在的房间信息,因此必须传达一列指令,使无论A君身处哪个房间,都能到达明亮的房间。
在那样的指示中,请回答最短的一个的长度。
约束
- 2 \leq N \leq 100
- 1 \leq M \leq min(16, N-1)
- 1 \leq K \leq N
- 1 \leq D_i \leq N
- D_i 都是不同的
- 1 \leq v_{i, j} \leq N
- 所有的暗房至少可以到达一个明亮的房间
输入格式
N M K
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}
输出格式
示例输入 1
4 2 2 1 2 2 4 3 1 4 2 1 3
示例输出 1
2
[原题图片已从来源服务器移除:原图]
1, 1
- 如果A先生的初始位置是房间1,那么他第二步将到达房间3。
- 如果A先生的初始位置是2号房间,那么他第一步就会到达3号房间。
示例输入 2
3 2 2 1 2 2 3 1 2 2 1
示例输出 2
3
如果您给出指令 2, 1, 2,
- 如果A先生的初始位置是房间1,那么他第一步就会到达房间3。
- 如果A先生的初始位置是房间2,他将在第三次移动时到达房间3。
示例输入 3
6 3 3 1 2 3 4 1 1 2 5 2 3 3 6 4 4 4 5 5 5 6 6 6
示例输出 3
3
请小心未连接的情况、具有自边缘的情况以及具有多个边缘的情况。