54. Граф подстрок

Антон стажируется в группе обработки комментариев и отзывов. Для проверки гипотезы об автоматической генерации текстов Антон должен построить граф подстрок существующих текстов.

Антон берёт все имеющиеся у него слова и действует следующим образом:

• слово $S=s_{1}s_{2} ... s_{n-1}s_{n}$ образует $n-2$ слова длины 3: $w_{1}=s_{1}s_{2}s_{3}$, $w_{2}=s_{2}s_{3}s_{4}$, $w_{3}=s_{3}s_{4}s_{5}$ $\ldots$ $w_{n-2}=s_{n-2}s_{n-1}s_{n}$;
• если для какого-то из слов $w_{i}$ еще нет вершины в графе, то она создается;
• для каждой пары слов $(w_{i},w_{i+1})$ добавляется ориентированное ребро веса 1, или увеличивается вес существующего ребра на 1.

Таким образом получается граф $G$ с $v$ вершинами и $e$ ориентированными рёбрами. Между некоторыми вершинами может быть несколько дуг (от $a$ к $b$ и от $b$ к $a$).

По заданному набору слов помогите Антону найти количество вершин в графе и вывести ориентированные рёбра между вершинами.

В первой строке записано одно целое число $T$ ($1 \le T \le 40\,000$) — количество слов, имеющихся у Антона.

В каждой из $T$ следующих строк записано одно слово $S_i$ ($4 \le |S_i| \le 30$). Все слова состоят из строчных букв английского алфавита.

В первой строке выведите количество вершин $v$ в графе $G$.

Во второй строке выведите количество пар вершин $e$, между которыми есть ориентированные ребра.

В каждой из следующих $e$ строк выведите слово $w_s$, соответствующее началу ребра, затем слово $w_f$, соответствующее концу ребра, и вес ориентированного ребра из вершины $w_s$ в $w_f$.

Рёбра вы можете перечислить в произвольном порядке.