Description

给定一个有向无环图，其中有 $n$ 个顶点和 $m$ 条边。每条边都有一个标记（由小写字母组成的字符串；可能为空字符串）。我们将“路径的标记”定义为这条路径上各边标记按路径顺序拼接而成的字符串。若从起点顶点 $s$ 到目标顶点 $t$ 存在多条路径，则其中最小的路径指的是其标记在所有路径的标记中按字典序最小的那条。请你编写一个程序，对于给定的起点 $s$，输出从 $s$ 到每个顶点 $t$ 的最小路径。

Input Format

第一行包含四个整数，分别是 $n$（顶点数）、$m$（边数）、$d$（字符串 $A$ 的长度，见下文）、$s$（起点的编号）。顶点编号为 $1$ 到 $n$。

第二行给出一个字符串 $A$，长度正好为 $d$，所有字符均为小写英文字母。图中所有边的标记都是字符串 $A$ 的子串。

接下来 $m$ 行描述各条边。第 $i$ 行描述第 $i$ 条边，包含四个整数：$u_i$（该边的起点）、$v_i$（该边的终点）、$p_i$ 和 $\ell_i$。其中最后两个数表示该边的标记是字符串 $A$ 的一个子串：它从 $A$ 的第 $p_i$ 个字符开始，长度为 $\ell_i$。这里我们认为 $A$ 的字符编号从 $1$ 到 $d$。

Output Format

输出 $n$ 行，第 $t$ 行（$t = 1, \dots, n$）描述从 $s$ 到 $t$ 的最小路径。

• 如果从 $s$ 到 $t$ 不存在路径，则这一行只输出整数 $0$。
• 否则，先输出路径上的顶点数（包含 $s$ 与 $t$），随后输出该路径上所有顶点的编号，按路径顺序排列，彼此间以空格分隔。

如果存在多条合法解，输出任意一条均可。

5 7 6 3
abcbca
3 2 1 1
2 1 5 1
2 5 4 2
3 1 1 2
3 4 3 2
1 4 6 1
5 4 5 2

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

Hint

注释

在这个样例中，边 $3 \rightarrow 1$ 的标记是 "ab"；边 $1 \rightarrow 4$ 的标记是 "a"；因此从 $3$ 到 $4$ 的最小路径是 $3 \rightarrow 1 \rightarrow 4$，其标记为 "aba"。

输入限制

• $1 \leq s \leq n \leq 600$
• $1 \leq m \leq 2000$
• $1 \leq d \leq 10^6$
• $1 \leq u_i \leq n$，$1 \leq v_i \leq n$，且 $u_i \neq v_i$（对所有 $i = 1, \dots, m$ 成立）
• $1 \leq p_i$，$0 \leq \ell_i$，并且 $p_i + \ell_i - 1 \leq d$（对所有 $i = 1, \dots, m$ 成立）
• 图是无环的，且不存在平行边（即若 $i \neq j$，则有 $u_i \neq u_j$ 或 $v_i \neq v_j$）。

翻译由 ChatGPT-5 完成