CF590E.Birthday

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Today is birthday of a Little Dasha — she is now 8 years old! On this occasion, each of her nn friends and relatives gave her a ribbon with a greeting written on it, and, as it turned out, all the greetings are different. Dasha gathered all the ribbons and decided to throw away some of them in order to make the remaining set stylish. The birthday girl considers a set of ribbons stylish if no greeting written on some ribbon is a substring of another greeting written on some other ribbon. Let us recall that the substring of the string ss is a continuous segment of ss .

Help Dasha to keep as many ribbons as possible, so that she could brag about them to all of her friends. Dasha cannot rotate or flip ribbons, that is, each greeting can be read in a single way given in the input.

输入格式

The first line of the input contains integer nn ( 1<=n<=7501<=n<=750 ) — the number of Dasha's relatives and friends.

Each of the next nn lines contains exactly one greeting. Each greeting consists of characters 'a' and 'b' only.

The total length of all greetings won't exceed 1000000010000000 characters.

输出格式

In the first line print the maximum size of the stylish set. In the second line print the numbers of ribbons involved in it, assuming that they are numbered from 11 to nn in the order they appear in the input. If there are several stylish sets of the maximum size, print any of them.

输入输出样例

  • 输入#1

    5
    abab
    aba
    aabab
    ababb
    bab
    

    输出#1

    2
    2 5
    

说明/提示

In the sample, the answer that keeps ribbons 3 and 4 is also considered correct.

首页