92bcdf15.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

int main()
{
#define PANIC               \
    {                       \
        puts("impossible"); \
        return 0;           \
    }

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n;

    string str;
    cin >> str;

    auto match = [&](const string &cur, const string &str) {
        if (cur.length() > str.length())
        {
            return false;
        }

        const char *C = cur.data(), *S = str.data();
        const size_t lenC = cur.length(), lenS = str.length();

        for (size_t i = 0UL, j = 0UL; i < lenC; ++i, ++j)
        {
            for (; j < lenS && C[i] != S[j]; ++j)
                ;
            if (j == lenS)
            {
                return false;
            }
        }

        return true;
    };

    auto groupMatch = [&](const vector<const string *> &vec, const string &str) {
        if (vec.empty())
        {
            return true;
        }
        return match(*vec.back(), str);
    };

    vector<string> vec(n);

    for (auto &cur : vec)
    {
        cin >> cur;
        if (!match(cur, str))
        {
            PANIC;
        }
    }

    sort(vec.begin(), vec.end(), [&](const string &x, const string &y) {
        return x.length() < y.length();
    });
    // alive;

    vector<const string *> f, g, t;

    for (const auto &cur : vec)
    {
        // alive;
        bool u = groupMatch(f, cur),
             v = groupMatch(g, cur);
        // alive;
        if (!u && !v)
        {
            PANIC;
        }
        if (u && v)
        {
            if (groupMatch(t, cur))
            {
                t.emplace_back(&cur);
            }
            else
            {
                f.emplace_back(&cur);
                g.insert(g.end(), t.begin(), t.end());
                t.clear();
            }
        }
        else if (u)
        {
            f.emplace_back(&cur);
            g.insert(g.end(), t.begin(), t.end());
            t.clear();
        }
        else
        {
            g.emplace_back(&cur);
            f.insert(f.end(), t.begin(), t.end());
            t.clear();
        }
    }

    g.insert(g.end(), t.begin(), t.end());
    t.clear();

    cout << f.size() << " " << g.size() << "\n";

    for (const auto &ptr : f)
    {
        cout << *ptr << "\n";
    }

    for (const auto &ptr : g)
    {
        cout << *ptr << "\n";
    }

#undef PANIC
}