Codeforces Round 327 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

graph matchings

strings

*3200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Birthday

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputToday is birthday of a Little Dasha — she is now 8 years old! On this occasion, each of her *n* 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 *s* is a continuous segment of *s*.

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.

Input

The first line of the input contains integer *n* (1 ≤ *n* ≤ 750) — the number of Dasha's relatives and friends.

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

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

Output

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 1 to *n* in the order they appear in the input. If there are several stylish sets of the maximum size, print any of them.

Examples

Input

5

abab

aba

aabab

ababb

bab

Output

2

2 5

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/13/2024 06:29:21 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|