Aho Corasick

각각 영문 소문자로 이루어진 문자열 $S_0, \dots, S_{N-1}$이 주어진다. 다음 설명에 따라 이 문자열들로 구성한 트라이의 정보를 출력한다.

• $P_{i,j}$는 $S_i$의 길이가 $j$인 접두사를 나타낸다. (여기서 $0 \leq j \leq |S_i|$)
• 집합 $P$을 $P=\lbrace P_{i,j}\mid 0\leq i<N, 0\leq j\leq |S_i|\rbrace$으로 정의한다. $n = |P|$라 하자.
• $(S_0, \dots, S_{N-1})$의 트라이는 $P$의 원소에 대응하는 $n$개의 정점으로 이루어진 트리이다. 트라이의 각 정점 $v$은 어떤 $\mathrm{str}(v) \in P$에 대응한다.
  • $\mathrm{str}(v) = P_{i,j}$를 만족하도록 $(i, j)$을 선택할 때, $i$이 최소화된 상태에서 $(i, j)$의 사전순으로 정점에 번호 $0, 1, \dots, n-1$를 부여한다. 특히, $\mathrm{str}(0)$은 빈 문자열이다.
• 각 정점 $v$ ($1 \leq v < n$)에 대해, $p_v$은 부모 정점의 번호를 나타낸다. 다시 말해, $p_v$는 $\mathrm{str}(v)$에서 마지막 문자를 제거하여 얻은 문자열에 대응하는 정점의 번호이다.
• 각 정점 $v$ ($1 \leq v \leq n$)에 대해, $s_v$은 접미사 링크의 도착점을 나타낸다. 즉, $s_v$은 $\mathrm{str}(v)$의 접미사 중 $P$에 속하고 $\mathrm{str}(v)$보다 짧은 가장 긴 접미사에 대응하는 정점의 번호이다.

$n$의 값을 출력하고, 각 정점 $v$ ($1 \leq v < n$)에 대해 $p_v$와 $s_v$를 출력한다. 또한 각 $i = 0, 1, \dots, N-1$에 대해 $S_i$에 대응하는 정점의 번호를 출력한다.

제약 조건

• $1 \leq N \leq 1000000$
• $1 \leq |S_i| \leq 1000000$
• $1 \leq \sum_{0\leq i<N}|S_i| \leq 1000000$
• $S$의 각 문자는 영문 소문자이다.

$N$
$S_0$
$\vdots$
$S_{N-1}$

$n$
$p_1$ $s_1$
$\vdots$
$p_{n-1}$ $s_{n-1}$
$v_0$ $\ldots$ $v_{N-1}$