XCKLT

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define task "XCKLT"
#define vt vector

using namespace std;
using ll = long long;

const int N = 5e2 + 2;
const int Inf = 1e9 + 7;
string a, b, c;
int m, n, p;
int f[N * 2][N];
bool can[N * 2][N];

void Read()
{
    cin >> a >> b >> c;
    m = a.size();
    n = b.size();
    p = c.size();
}

void Sub_1()
{
    if (a == c || b == c)
    {
        cout << "TRETRAU";
        return;
    }
    if (a != b)
        cout << "2\n"
             << (a + b);
    else
        cout << "1\n"
             << a;
}

string Trace_2(vt<vt<vt<vt<char>>>> par, int i, int j, int t, int h)
{
    string s;
    while (i != 0)
    {
        if (a[j] == par[i][j][t][h] || b[t] == par[i][j][t][h] || c[h] == par[i][j][t][h])
        {
            s.push_back(par[i][j][t][h]);
            j -= a[j] == s.back();
            t -= b[t] == s.back();
            h -= c[h] == s.back();
        }
        --i;
    }
    reverse(s.begin(), s.end());
    return s;
}

int LCS(const string &s, const string &p)
{
    for (int i = 1; i <= (int)s.size(); ++i)
        for (int j = 1; j <= (int)p.size(); ++j)
        {
            if (s[i - 1] == p[j - 1])
                f[i][j] = f[i - 1][j - 1] + 1;
            else
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    return f[s.size()][p.size()];
}

void Sub_2()
{
    a = " " + a;
    b = " " + b;
    c = " " + c;
    vt<vt<vt<vt<bool>>>> dp(m + n + 1, vt<vt<vt<bool>>>(m + 1, vt<vt<bool>>(n + 1, vt<bool>(p + 1, 0))));
    vt<vt<vt<vt<char>>>> par(m + n + 1, vt<vt<vt<char>>>(m + 1, vt<vt<char>>(n + 1, vt<char>(p + 1, '*'))));
    dp[0][0][0][0] = 1;
    for (int i = 1; i <= m + n; ++i)
        for (int j = 0; j <= m; ++j)
            for (int t = 0; t <= n; ++t)
                for (int h = 0; h <= p; ++h)
                {
                    /*if(dp[i - 1][j][t][h]){
                        dp[i][j][t][h] = 1;
                        continue;
                    }*/
                    vector<char> u;
                    if (j > 0)
                        u.push_back(a[j]);
                    if (t > 0)
                        u.push_back(b[t]);
                    if (h > 0)
                        u.push_back(c[h]);
                    for (char k : u)
                    {
                        register int x = j - (a[j] == k),
                                     y = t - (b[t] == k),
                                     z = h - (c[h] == k);
                        if (dp[i - 1][x][y][z] && ((!dp[i - 1][x][y][h]) || h == p || c[h + 1] != k))
                        {
                            dp[i][j][t][h] = 1;
                            par[i][j][t][h] = k;
                            break;
                        }
                    }
                }
    for (int i = 1; i <= m + n; ++i)
    {
        for (int j = 0; j < p; ++j)
            if (dp[i][m][n][j])
            {
                string s = Trace_2(par, i, m, n, j);
                if (LCS(s, c.substr(1, p)) < p)
                {
                    cout << i << "\n"
                         << s;
                    return;
                }
            }
    }
    cout << "TRETRAU";
}

string Trace_3(vt<vt<vt<char>>> par, int j, int t, int h)
{
    string s;
    while (j != 0 || t != 0 || h != 0)
    {
        if (a[j] == par[j][t][h] || b[t] == par[j][t][h] || c[h] == par[j][t][h])
        {
            s.push_back(par[j][t][h]);
            j -= a[j] == s.back();
            t -= b[t] == s.back();
            h -= c[h] == s.back();
        }
    }
    reverse(s.begin(), s.end());
    return s;
}

void Sub_3()
{

    a = " " + a;
    b = " " + b;
    c = " " + c;
    vt<vt<vt<int>>> dp(m + 1, vt<vt<int>>(n + 1, vt<int>(p + 1, Inf)));
    vt<vt<vt<char>>> par(m + 1, vt<vt<char>>(n + 1, vt<char>(p + 1, '*')));
    dp[0][0][0] = 0;
    for (int j = 0; j <= m; ++j)
        for (int t = 0; t <= n; ++t)
            for (int h = 0; h <= p; ++h)
            {
                vector<char> u;
                if (j > 0)
                    u.push_back(a[j]);
                if (t > 0)
                    u.push_back(b[t]);
                if (h > 0)
                    u.push_back(c[h]);
                for (char k : u)
                {
                    register int x = j - (a[j] == k),
                                 y = t - (b[t] == k),
                                 z = h - (c[h] == k);
                    if (dp[j][t][h] > dp[x][y][z] + 1 && (dp[x][y][h] == Inf || h == p || c[h + 1] != k))
                    {
                        dp[j][t][h] = dp[x][y][z] + 1;
                        par[j][t][h] = k;
                    }
                }
            }
    for (int i = 0; i < p; ++i)
        if (dp[m][n][i] != Inf)
        {
            string s = Trace_3(par, m, n, i);
            if (LCS(s, c.substr(1, p)) < p)
            {
                cout << dp[m][n][i] << "\n"
                     << s;
                return;
            }
        }
    cout << "TRETRAU";
}

int32_t main()
{
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    if (a.size() == 1 && b.size() == 1 && c.size() == 1)
        Sub_1();
    else if (1ll * (m + n) * m * n * p * 26 <= 5e7)
        Sub_2();
    else
        Sub_3();
}