← 返回题目列表

Codeforces · 1090/K

K. 心灵的右扩张

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Right Expansion Of The Mind - 原题 PDF 第 1 页
原题PDF第15页
Right Expansion Of The Mind - 原题 PDF 第 2 页
原题PDF第16页
可复制的 PDF 提取文本
XIX Russia Team Open, High School Programming Contest
              St Petersburg, Barnaul, Tbilisi, Almaty, Kremenchug, Sochi, December 9, 2018
Problem K. Right Expansion Of The Mind

    Time limit:        2 seconds
    Memory limit:     512 megabytes

One day n people decided to expand their mind.

Initially, the mind of the i-th person is two strings si and ti consisting of lowercase English letters. After
the expansion, the mind of the person becomes an infinite to the right string wi = si + ti + ti + · · · . That
is, wi is a concatenation of si and the infinite number of ti. For example, if si = mi and ti = nd, the
corresponding wi = mindndndnd . . . .

Two persons with expanded mind are interested in each other, if the mind of the first person forms a
subsequence of the mind of the second person, and the mind of the second person forms a subsequence of
the mind of the first person. The infinite string a is called a subsequence of the infinite string b if there is
an infinite sequence of indices 1 ≤i1 < i2 < i3 < . . ., such that for each j it is aj = bij. For example, the
infinite string “baaa. . . ” is a subsequence of an infinite string “cabababab. . . ”.

After having the mind expanded, people decided to split into groups in such way, that any two persons
in one group are interested in each other. Your task is to split them into the groups, so that the number
of groups is minimal possible.

Input

The first line contains one integer n — the number of people that have decided to get their mind expanded
(1 ≤n ≤100 000).

Each of the following n lines contains two non-empty strings si and ti, consisting of lowercase English
letters. They represent the minds of every person before the mind expansion.

It is guaranteed that the total length of all strings doesn’t exceed 1 000 000.

Output

The first line must contain one integer — the minimum number of groups.

Then print each group in the following way: first print the number of people in this group and then the
indices of them.

Each of the indices must be printed exactly once. The groups and indices of the people in the group can
be printed in any order. If there are multiple ways to split the people, you can print any of them.

Examples

             standard input                         standard output
 5                                       3
 ab ab                                   3 1 2 3
 ababab ab                               1 4
 a abb                                   1 5
 x y
 z w
 3                                       2
 kokoko tlin                             1 1
 koko kotlin                             2 2 3
 ko kokotlin





                                        Page 15 of 18

XIX Russia Team Open, High School Programming Contest
              St Petersburg, Barnaul, Tbilisi, Almaty, Kremenchug, Sochi, December 9, 2018

Note

In the first example the expanded minds of the people look as follows:

   • “abababab...”
   • “abababab...”
   • “aabbabbabb...”
   • “xyyyyyy...”
   • “zwwwwww...”

Neither person 4 nor 5 are interested in anybody else. However, the first three people show pairwise
interest in each other. Hence it is possible to have the groups {1, 2, 3}, {4}, {5}.





                                        Page 16 of 18