Labelled Paths

We are given a directed acyclic graph with $n$ vertices and $m$ edges. Each edge has a label, a string of lowercase letters that may be empty. The label of a path is the concatenation of the edge labels along the path, in path order. The smallest path from a start vertex $s$ to a destination vertex $t$ is the path whose label is lexicographically smallest among all paths from $s$ to $t$. For a given $s$, output the smallest path from $s$ to every vertex $t$.

The first line contains four integers $n$, $m$, $d$, and $s$. Here $d$ is the length of the string $A$ described below. Vertices are numbered from 1 to $n$.

The second line contains the string $A$, exactly $d$ lowercase English letters. Every edge label is a substring of $A$.

Each of the next $m$ lines contains four integers $u_i$, $v_i$, $p_i$, and $\ell_i$. The $i$-th edge goes from $u_i$ to $v_i$, and its label is the substring of $A$ that starts at the $p_i$-th character and has length $\ell_i$. The characters of $A$ are indexed from 1 to $d$.

Print $n$ lines. The $t$-th line describes the smallest path from $s$ to $t$. If no path from $s$ to $t$ exists, print only the integer 0. Otherwise, print the number of vertices on the path (including $s$ and $t$), followed by the vertices in path order, separated by spaces. If several solutions exist, any of them is accepted.

• $1 \le s \le n \le 600$
• $1 \le m \le 2000$
• $1 \le d \le 10^6$
• $1 \le u_i \le n$, $1 \le v_i \le n$, $u_i \ne v_i$ for all $i$
• $1 \le p_i$, $0 \le \ell_i$, $p_i + \ell_i - 1 \le d$ for all $i$
• The graph is acyclic and has no parallel edges. That is, for $i \ne j$, $u_i \ne u_j$ or $v_i \ne v_j$.

In this example, the edge $3 \to 1$ has label ab and the edge $1 \to 4$ has label a. The smallest path from 3 to 4 is $3 \to 1 \to 4$, with label aba.