회문 트리

영문 소문자로 이루어진 문자열 $S$이 주어진다. 다음 설명에 따라 $S$의 회문 트리(회문 문자열 트리 또는 팰린드롬 트리라고도 한다)의 정보를 출력한다.

• $P$를 $S$의 비어 있지 않은 회문 부분 문자열의 집합이라 하고, $n = |P|$라 하자.
• $S$의 회문 트리는 $2$개의 트리로 구성되며, 이 트리들은 $P$의 원소에 대응하는 $n$개의 정점과 ODD 및 EVEN라고 하는 두 특수 정점을 포함한다.
• 회문 트리의 정점에 다음과 같이 번호를 매긴다:
  • ODD의 번호는 $-1$이고, EVEN의 번호는 $0$이다.
  • 그 밖의 각 정점 $v$는 어떤 $\mathrm{str}(v) \in P$에 대응한다. $\mathrm{str}(v) = S_i \cdots S_{j-1}$에 대해, $(i,j)$는 $j$가 최소가 되도록 선택하고, $j$의 오름차순으로 정점에 번호 $1, 2, \ldots, n$을 부여한다.
  • 각 정점 $v$ ($1 \leq v \leq n$)에 대해, $p_v$를 부모 정점의 번호라 하자. 즉, $p_v$는 $\mathrm{str}(v)$의 첫 문자와 마지막 문자를 제거하여 얻은 회문에 대응하는 정점의 번호이다. 단, $|\mathrm{str}(v)| = 2$이면 부모는 EVEN (번호 $0$)이고, $|\mathrm{str}(v)| = 1$이면 부모는 ODD (번호 $-1$)이다.
• 각 정점 $v$ ($1 \leq v \leq n$)에 대해, $s_v$를 $v$에서 나가는 접미사 링크의 도착점이라 하자. 즉, $s_v$은 $\mathrm{str}(v)$의 비어 있지 않은 회문 접미사 중 $\mathrm{str}(v)$보다 짧은 가장 긴 것에 대응하는 정점의 번호이다. 그러한 회문 접미사가 존재하지 않으면, 접미사 링크의 도착점은 EVEN (번호 $0$)로 정의한다.

$n$을 출력하고, 각 $v$ ($1 \leq v \leq n$)에 대해 $p_v, s_v$를 출력한다.

또한 각 $i = 1, 2, \ldots, |S|$에 대해, 길이가 $i$인 접두사 $S_0 \cdots S_{i-1}$의 가장 긴 회문 접미사에 대응하는 정점의 번호를 출력한다.

제약 조건

• $1 \leq |S| \leq 1000000$
• $S$의 각 문자는 영문 소문자이다.

$S$

$n$
$p_1$ $s_1$
$\vdots$
$p_n$ $s_n$
$v_1$ $\ldots$ $v_{|S|}$