357_substring_graph

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

Description

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

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

• слово $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$).

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

Input Format:

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

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

Output Format:

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

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

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

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

Example Test Cases

Example 1

Input:

2
aaaaaaaaaaaaa
aaabbbaaabbba

Output:

6
7
aaa aaa 10
aaa aab 2
aab abb 2
abb bbb 2
bbb bba 2
bba baa 1
baa aaa 1

Example 2

Input:

2
abab
baba

Output:

2
2
aba bab 1
bab aba 1

Example 3

Input:

1
qwertyqwertyqwertyqwertyqwerty

Output:

6
6
qwe wer 5
wer ert 5
ert rty 5
rty tyq 4
tyq yqw 4
yqw qwe 4

Tags: standard library, graph theory, strings