Задача №114487. Расширение сознания вправо
Как-то раз \(n\) человек решили расширить своё сознание.
Изначально сознание \(i\)-го человека — это две строки \(s_i\) и \(t_i\), состоящие из маленьких латинских букв. После расширения сознание человека становится бесконечной вправо строкой \(w_i=s_i+t_i+t_i+\cdots\). То есть, \(w_i\) — это конкатенация \(s_i\) и бесконечного количества \(t_i\). Например, если \(s_i=\texttt{mi}\), \(t_i=\texttt{nd}\), то \(w_i=\texttt{mindndndnd}\dots\).
Два человека с расширенным сознанием интересны друг другу , если сознание первого человека является подпоследовательностью сознания второго, а сознание второго является подпоследовательностью сознания первого. Бесконечная строка \(a\) называется подпоследовательностью бесконечной строки \(b\), если существует такая бесконечная последовательность индексов \(1 \leq i_1 < i_2 < i_3 < \ldots\), что для любого \(j\) выполнено \(a_j=b_{i_j}\). Например, « baaa ...» — подпоследовательность « cabababab ...».
После расширения сознания люди решили разбиться на группы таким образом, чтобы в каждой группе любые два человека были интересны друг другу. Ваша задача — разбить их на группы так, чтобы получилось минимально возможное число групп.
Первая строка содержит одно целое число \(n\) (\(1 \le n \le 100\,000\)) — количество людей, которые решили расширить своё сознание.
Каждая из следующих \(n\) строк содержит две непустые строки \(s_i\) и \(t_i\), состоящие только из строчных латинских букв — сознания людей до расширения.
Гарантируется, что суммарная длина всех строк не превосходит \(1\,000\,000\).
В первой строке выведите одно целое число — минимальное количество групп в разбиении.
Затем выведите каждую группу следующим образом: сначала выведите количество людей в этой группе, а затем индексы этих людей во входных данных.
Каждый из индексов нужно вывести ровно один раз. Группы и индексы внутри группы можно выводить в любом порядке. Если существует несколько оптимальных разбиений, то можно вывести любое из них.
В первом примере сознания людей после расширения сознания выглядят следующим образом:
- « abababab... »;
- « abababab... »;
- « aabbabbabb... »;
- « xyyyyyy... »;
- « zwwwwww... ».
Ни человек \(4\), ни \(5\) не будут интересны кому-нибудь ещё. Но первые три человека попарно интересны друг другу, а значит можно составить разбиение на группы \(\{1,2,3\}\), \(\{4\}\), \(\{5\}\).
5 ab ab ababab ab a abb x y z w
3 3 1 2 3 1 5 1 4
3 kokoko tlin koko kotlin ko kokotlin
2 1 1 2 2 3