主角已被省略,因为太短了。
给你一个有向无权图,没有循环,有 $$$n$$$ 个顶点,并且其中有一个路径(该路径不一定很简单),由 $$$p_1, p_2, \ldots, p_m$$$ 的 $$$m$$$ 顶点序列给出;对于每个 $$$1 \leq i < m$$$ ,都有一条从 $$$p_i$$$ 到 $$$p_{i+1}$$$ 的弧。
如果 $$$v$$$ 是 $$$p$$$ 的子序列,$$$v_1 = p_1$$$,$$$v_k = p_m$$$,并且 $$$p$$$ 是最短路径之一,则定义 $$$k$$$ 顶点的序列 $$$v_1, v_2, \ldots, v_k$$$ 为好按顺序穿过顶点 $$$v_1$$$、$$$\ldots$$$、$$$v_k$$$。
如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是序列 $$$b$$$ 的子序列。显然序列 $$$p$$$ 是好的,但你的任务是找到最短的好的子序列。
如果有多个最短的好子序列,则输出其中任何一个。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 图中的顶点数。
接下来的 $$$n$$$ 行通过邻接矩阵定义图:如果从顶点 $$$i$$$ 到顶点 $$$j$$$ 存在弧,则 $$$i$$$-st 行中的第 $$$j$$$ 个字符等于 $$$1$$$,否则等于 $$$0$$$。保证该图不包含循环。
下一行包含一个整数 $$$m$$$ ($$$2 \le m \le 10^6$$$) — 路径中的顶点数。
下一行包含 $$$m$$$ 整数 $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \le p_i \le n$$$) — 路径中的顶点序列。保证对于任何 $$$1 \leq i < m$$$ 存在从 $$$p_i$$$ 到 $$$p_{i+1}$$$ 的弧。
输出
在第一行输出一个整数 $$$k$$$ ($$$2 \leq k \leq m$$$) — 最短好子序列的长度。在第二行中输出 $$$k$$$ 整数 $$$v_1$$$, $$$\ldots$$$, $$$v_k$$$ ($$$1 \leq v_i \leq n$$$) - 子序列中的顶点。如果有多个最短子序列,则打印任何一个。任何两个连续的数字应该是不同的。
示例
输入 #1
4 0110 0010 0001 1000 4 1 2 3 4
输出 #1
3 1 2 4
输入 #2
4 0110 0010 1001 1000 20 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
输出 #2
11 1 2 4 2 4 2 4 2 4 2 4
输入 #3
3 011 101 110 7 1 2 3 1 3 2 1
输出 #3
7 1 2 3 1 3 2 1
输入#4
4 0110 0001 0001 1000 3 1 2 4
输出#4
2 1 4
注意
下面您可以看到第一个示例中的图表:
给定路径穿过顶点 $$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$。序列 $$$1-2-4$$$ 很好,因为它是给定路径的子序列,它的第一个和最后一个元素分别等于给定路径的第一个和最后一个元素,并且按顺序通过顶点 $$$1$$$、$$$2$$$ 和 $$$4$$$ 的最短路径是 $$$1-2-3-4$$$。请注意,子序列 $$$1-4$$$ 和 $$$1-3-4$$$ 不好,因为在这两种情况下,穿过这些序列顶点的最短路径都是 $$$1-3-4$$$。
在第三个示例中,图是完整的,因此其中任意两个连续元素不同的任何顶点序列定义了由相同数量的顶点组成的路径。
在第四个示例中,路径$$$1-2-4$$$和$$$1-3-4$$$是经过顶点$$$1$$$和$$$4$$$的最短路径。