Se consideră o mulțime S care conține N șiruri de caractere formate din litere mici ale alfabetului englezesc.

Un șir de caractere se numește interesant în raport cu celelalte șiruri ale mulțimii, dacă nu există un alt șir în mulțime care să-l conțină ca subșir. De exemplu, dacă mulțimea S conține șirurile abc, bde și abcdef, atunci singurul șir interesant este abcdef deoarece abc și bde nu îl conțin ca subșir. Mai mult, abc și bde sunt subșiruri în abcdef, deci nu sunt interesante.

Cerința

Fiind dată o mulțime S formată din N șiruri de caractere se cere:

1. Să se determine cel mai lung șir. Dacă sunt mai multe șiruri având aceeași lungime maximă, se cere cel mai mic din punct de vedere lexicografic.
2. Să se determine toate șirurile interesante din mulțimea S.

Date de intrare

Fișierul de intrare interesant.in conține pe prima linie două numere naturale p și N, despărțite prin spațiu. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe următoarele N linii, se găsesc șirurile de caractere, câte unul pe linie.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai cerința 1.

Se consideră o mulțime S care conține N șiruri de caractere formate din litere mici ale alfabetului englezesc.

Un șir de caractere se numește interesant în raport cu celelalte șiruri ale mulțimii, dacă nu există un alt șir în mulțime care să-l conțină ca subșir. De exemplu, dacă mulțimea S conține șirurile abc, bde și abcdef, atunci singurul șir interesant este abcdef deoarece abc și bde nu îl conțin ca subșir. Mai mult, abc și bde sunt subșiruri în abcdef, deci nu sunt interesante.

Cerința

Fiind dată o mulțime S formată din N șiruri de caractere se cere:

1. Să se determine cel mai lung șir. Dacă sunt mai multe șiruri având aceeași lungime maximă, se cere cel mai mic din punct de vedere lexicografic.
2. Să se determine toate șirurile interesante din mulțimea S.

Date de intrare

Fișierul de intrare interesant.in conține pe prima linie două numere naturale p și N, despărțite prin spațiu. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe următoarele N linii, se găsesc șirurile de caractere, câte unul pe linie.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai cerința 1.
În acest caz, în fișierul de ieșire interesant.out se va scrie cel mai lung șir dintre cele citite. Dacă există mai multe șiruri de aceeași lungime, se va scrie cel mai mic din punct de vedere lexicografic.
Dacă valoarea lui p este 2, se va rezolva numai cerința 2.
În acest caz, fișierul de ieșire interesant.out va conține pe prima linie o valoare K ce reprezintă numărul de șiruri interesante, iar pe următoarele K linii, șirurile interesante în ordinea în care apar în fișierul de intrare.

Restricții și precizări

• 2 ≤ N ≤ 200
• Lungimea unui șir va fi cuprinsă între 1 și 5000
• Un subșir al șirului de caractere C0C1C2 …Ck se definește ca fiind o succesiune de caractere Ci1Ci2Ci3…Cik, unde 0 ≤ i1 < i2 < i3 < … < ik ≤ k.
• Fișierul de intrare NU conține șiruri identice.
• Pentru rezolvarea corectă a primei cerințe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.

Exemplul 1

interesant.in

1 5
abcacaaz
ad
abcacaad
acd
zyt

interesant.out

abcacaad

Explicație

p=1
Fișierul de intrare conține 5 șiruri.
abcacaad este șirul de lungime maximă. Șirul abcacaaz are aceeași lungime, dar este mai mare din punct de vedere lexicografic.

• Atenție! Pentru acest test se rezolvă doar cerința 1.*

Exemplul 2

interesant.in

2 5
abcacaad
ad
zayyt
acd
zyt

interesant.out

2
abcacaad
zayyt

Explicație

p=2
Fișierul de intrare conține 5 șiruri.
ad, acd sunt subșiruri al lui abcacaad, iar zyt este subșir al lui zayyt

• Atenție! Pentru acest test se rezolvă doar cerința 2.*

#include <bits/stdc++.h>

using namespace std;

ifstream cin("interesant.in");
ofstream cout("interesant.out");

char m[201][5001];

bool subsir(char a[] , char b[])
{
    if(strlen(a) > strlen(b))
        return 0;
    else
    {
        int i = 0;
        for(int j = 0 ; b[j] ; ++j)
        {
            if(a[i]==b[j])
                i++;
            else if(strlen(a) - i > strlen(b) - j)
                    return 0;
        }
        if(i == strlen(a))
            return 1;
        return 0;
    }
}

int main()
{
    int t , n;
    cin >> t >> n;
    for(int i = 1 ; i <= n ; ++i)
        cin >> m[i];
    if(t==1)
    {
        int max=0;
        int ind;
        for(int i = 1 ; i <= n ; ++i)
        {
            if(strlen(m[i]) > max)
                max=strlen(m[i]) , ind = i;
            else if(strlen(m[i])==max)
                if(strcmp(m[ind] , m[i]) > 0)
                    ind=i;
        }
        cout << m[ind];
    }
    else
    {
        int vec[1001], p = 0;
        for(int i = 1 ; i <= n ; ++i)
        {
            bool ok = 1;
            for(int j = 1 ; j <= n ; ++j)
            {
                if(j != i && subsir(m[i] , m[j]))
                {
                    ok=0;
                }
            }
            if(ok)
                vec[++p]=i;
        }
        cout << p << endl;
        for(int i = 1 ; i <= p ; ++i)
            cout << m[vec[i]] << endl;
    }
    return 0;
}