CF1204C.Anna, Svyatoslav and Maps

The main characters have been omitted to be short.

You are given a directed unweighted graph without loops with $n$ vertexes and a path in it (that path is not necessary simple) given by a sequence $p_1, p_2, \ldots, p_m$ of $m$ vertexes; for each $1 \leq i \lt m$ there is an arc from $p_i$ to $p_{i+1}$.

Define the sequence $v_1, v_2, \ldots, v_k$ of $k$ vertexes as good, if $v$ is a subsequence of $p$, $v_1 = p_1$, $v_k = p_m$, and $p$ is one of the shortest paths passing through the vertexes $v_1$, $\ldots$, $v_k$ in that order.

A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements. It is obvious that the sequence $p$ is good but your task is to find the shortest good subsequence.

If there are multiple shortest good subsequences, output any of them.

为简洁起见，题目中省略了主要角色。

给定一个含 $n$ 个顶点的无环有向无权图，以及该图中的一条路径（该路径不一定是简单路径），由顶点序列 $p_1, p_2, \ldots, p_m$ 给出；对每个 $1 \leq i < m$，均存在一条从 $p_i$ 指向 $p_{i+1}$ 的有向边。

定义长度为 $k$ 的顶点序列 $v_1, v_2, \ldots, v_k$ 为“好”的，当且仅当：

• $v$ 是 $p$ 的一个子序列；
• $v_1 = p_1$，且 $v_k = p_m$；
• $p$ 是经过顶点 $v_1, \ldots, v_k$（按此顺序）的所有路径中最短者之一。

序列 $a$ 是序列 $b$ 的子序列，指 $a$ 可通过从 $b$ 中删除若干（可能为零个或全部）元素而得到。显然，序列 $p$ 本身是“好”的，但你的任务是找出最短的“好”子序列。

若存在多个最短的“好”子序列，输出其中任意一个即可。

The first line contains a single integer $n$ ($2 \le n \le 100$) — the number of vertexes in a graph.

The next $n$ lines define the graph by an adjacency matrix: the $j$-th character in the $i$-st line is equal to $1$ if there is an arc from vertex $i$ to the vertex $j$ else it is equal to $0$. It is guaranteed that the graph doesn't contain loops.

The next line contains a single integer $m$ ($2 \le m \le 10^6$) — the number of vertexes in the path.

The next line contains $m$ integers $p_1, p_2, \ldots, p_m$ ($1 \le p_i \le n$) — the sequence of vertexes in the path. It is guaranteed that for any $1 \leq i \lt m$ there is an arc from $p_i$ to $p_{i+1}$.

第一行包含一个整数 $n$（$2 \le n \le 100$）—— 图中顶点的数量。

接下来的 $n$ 行通过邻接矩阵定义该图：第 $i$ 行的第 $j$ 个字符为 $1$ 当且仅当存在一条从顶点 $i$ 指向顶点 $j$ 的有向边，否则为 $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 \lt m$，均存在一条从 $p_i$ 指向 $p_{i+1}$ 的有向边。

In the first line output a single integer $k$ ($2 \leq k \leq m$) — the length of the shortest good subsequence. In the second line output $k$ integers $v_1$, $\ldots$, $v_k$ ($1 \leq v_i \leq n$) — the vertexes in the subsequence. If there are multiple shortest subsequences, print any. Any two consecutive numbers should be distinct.

第一行输出一个整数 $k$（$2 \leq k \leq m$）——最短的“好”子序列的长度。
第二行输出 $k$ 个整数 $v_1$, $\ldots$, $v_k$（$1 \leq v_i \leq n$）——该子序列中的顶点。
若存在多个最短子序列，输出任意一个即可。任意两个相邻的数必须互不相同。

Below you can see the graph from the first example:

The given path is passing through vertexes $1$, $2$, $3$, $4$. The sequence $1-2-4$ is good because it is the subsequence of the given path, its first and the last elements are equal to the first and the last elements of the given path respectively, and the shortest path passing through vertexes $1$, $2$ and $4$ in that order is $1-2-3-4$. Note that subsequences $1-4$ and $1-3-4$ aren't good because in both cases the shortest path passing through the vertexes of these sequences is $1-3-4$.

In the third example, the graph is full so any sequence of vertexes in which any two consecutive elements are distinct defines a path consisting of the same number of vertexes.

In the fourth example, the paths $1-2-4$ and $1-3-4$ are the shortest paths passing through the vertexes $1$ and $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$ 的最短路径。