回文树（Eertree）

给定一个由小写英文字母组成的字符串 $S$ 。请按照下面的描述，输出 $S$ 的回文树（eertree，也称为回文树、palindromic tree 或 palindrome tree）的信息。

设 $P$ 为 $S$ 的所有非空回文子串组成的集合，令 $n = |P|$ 。
$S$ 的回文树由 $2$ 棵树组成，其中包含 $n$ 个与 $P$ 中元素一一对应的顶点，以及两个称为 ODD 和 EVEN 的特殊顶点。
回文树的顶点编号方式如下：
- ODD 的编号为 $-1$ ，EVEN 的编号为 $0$ 。
- 其他每个顶点 $v$ 都对应某个 $\mathrm{str}(v) \in P$ 。对于 $\mathrm{str}(v) = S_i \cdots S_{j-1}$ ，按 $j$ 的升序为这些顶点分别赋予编号 $1, 2, \ldots, n$ ，其中 $(i,j)$ 的选取使得 $j$ 最小。
- 对每个顶点 $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}$ 的最长回文后缀所对应的顶点编号。

$S$

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

abaa

aaaaaaa

7
-1 0
0 1
1 2
2 3
3 4
4 5
5 6
1 2 3 4 5 6 7

abaccabacacca

11
-1 0
-1 0
2 1
-1 0
0 4
5 1
6 2
7 3
3 4
4 1
1 4
1 2 3 4 5 6 7 8 9 10 11 5 6

Library Checker（yosupo06） eertree