This page is still under construction.

Parts of this page are still being built. What you see may change.

First!

Time limit1sMemory limit128 MB

Summary
Given up to 30000 strings, find every string that can become lexicographically smallest under some permutation of the 26-letter alphabet.
Level

Hard8 of 10

Topics
String, Trie, Graph, Topological sort
Solved
No attempts yet

Problem

Bessie is playing with strings. She noticed that by changing the order of the alphabet she can make some strings come before all the others in lexicographic (dictionary) order.

For example, given the strings omm, moo, mom, and ommnom, she can make mom appear first using the standard alphabet, and she can make omm appear first using the alphabet abcdefghijklonmpqrstuvwxyz. However, no ordering of the alphabet makes moo or ommnom appear first.

Help Bessie by determining which of the input strings can be made lexicographically first by rearranging the order of the alphabet.

To decide whether string XX comes before string YY, find the first index jj at which they differ. If no such index exists, then XX comes before YY when XX is shorter than YY. Otherwise, XX comes before YY when X[j]X[j] appears earlier in the alphabet than Y[j]Y[j].

Input

  • Line 1: A single integer NN (1≤N≤300001 \le N \le 30000), the number of strings.
  • Lines 2 through N+1N+1: Each line contains one non-empty string. The total number of characters across all strings is at most 300000300000. Every character is a lowercase letter from a to z. No two input strings are identical.

Output

  • Line 1: A single integer KK, the number of strings that can be made lexicographically first.
  • Lines 2 through K+1K+1: The KK qualifying strings, printed in the same order in which they appear in the input.

Hint

With the standard alphabet, mom is the lexicographically smallest of the four sample strings, so mom can be first. Using the alphabet abcdefghijklonmpqrstuvwxyz (where o precedes n), omm becomes smallest, so omm can be first. No reordering of the alphabet can make moo or ommnom first, so exactly two strings qualify.

Examples3

  1. Example 1

    Input
    4
    omm
    moo
    mom
    ommnom
    
    Expected output
    2
    omm
    mom
    
  2. Example 2

    Input
    1
    a
    
    Expected output
    1
    a
    
  3. Example 3

    Input
    3
    a
    b
    c
    
    Expected output
    3
    a
    b
    c