Problems
Суффиксное дерево
Суффиксное дерево
Дана строка \textbf{s}. Постройте сжатое суффиксное дерево для строки \textbf{s} и выведите его.
Найдите такое дерево, которое содержит минимальное количество вершин.
\InputFile
В первой строке записана строка \textbf{s} (\textbf{1} ≤ \textbf{|s|} ≤ \textbf{10^5}), последний символ строки доллар "\textbf{\$}", остальные символы строки маленькие латинские буквы.
\OutputFile
Пронумеруйте вершины дерева от \textbf{0} до \textbf{n-1} в порядке обхода в глубину, обходя поддеревья в порядке лексикографической сортировки исходящих из вершины ребер. Используйте ASCII-коды символов для определения их порядка.
В первой строке выведите целое число \textbf{n} --- количество вершин дерева. В следующих \textbf{n-1} строках выведите описание вершин дерева, кроме корня, в порядке увеличения их номеров.
Описание вершины дерева \textbf{v} состоит из трех целых чисел: \textbf{p}, \textbf{lf}, \textbf{rg}, где \textbf{p} (\textbf{0} ≤ \textbf{p} < \textbf{n}, \textbf{p} ≠ \textbf{v}) --- номер родителя текущей вершины. На ребре, ведущем из \textbf{p} в \textbf{v}, написана подстрока \textbf{s\[lf...rg-1\]} (\textbf{0} ≤ \textbf{lf} < \textbf{rg} ≤ \textbf{|s|}).
\Note
\textit{Подстрокой} \textbf{s\[l...r\]} (\textbf{0} ≤ \textbf{l} ≤ \textbf{r} < \textbf{|s|}) строки \textbf{s = s_0s_1...s_\{|s|-1\}} (где \textbf{|s|} --- длина строки \textbf{s}) называется строка \textbf{s_ls_\{l+1\}...s_r}.
Input example #1
aaa$
Output example #1
7 0 3 4 0 0 1 2 3 4 2 1 2 4 3 4 4 2 4
Input example #2
b$
Output example #2
3 0 1 2 0 0 2
Input example #3
ababa$
Output example #3
10 0 5 6 0 0 1 2 5 6 2 1 3 4 5 6 4 3 6 0 1 3 7 5 6 7 3 6