← 返回题目列表

AtCoder · icpc2015summer_day2_d

D. 漆黑的房间

中文机器翻译题面 查看原题

问题陈述

我醒来时,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

请小心未连接的情况、具有自边缘的情况以及具有多个边缘的情况。