#include <bits/stdc++.h>
#include "hieroglyphs.h"
using namespace std;
int N, M;
vector<int> lcs(vector<int> s, vector<int> t) {
int P_LCS[N+2][M+2] = {};
int S_LCS[N+2][M+2] = {};
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
P_LCS[i][j] = max({P_LCS[i-1][j], P_LCS[i][j-1], P_LCS[i-1][j-1] + (s[i-1] == t[j-1])});
}
}
for (int i = N; i >= 1; i--) {
for (int j = M; j >= 1; j--) {
S_LCS[i][j] = max({S_LCS[i+1][j], S_LCS[i][j+1], S_LCS[i+1][j+1] + (s[i-1] == t[j-1])});
}
}
vector<int> res;
int x = N, y = M;
while (x > 0 && y > 0) {
if (max(P_LCS[x-1][y], P_LCS[x][y-1]) == P_LCS[x][y]-1) {
res.push_back(s[x-1]);
x--, y--;
} else if (P_LCS[x][y] == P_LCS[x-1][y]) {
x--;
} else {
y--;
}
}
reverse(res.begin(), res.end());
if (res.size() == 0) return {};
bool has_two_lcs = false;
int idx = 0;
for (int i = 1; i <= N; i++) {
if (s[i-1] == res[idx]) {
int mx = 0;
for (int j = 1; j < M; j++) {
mx = max(mx, S_LCS[i-1][j] + P_LCS[i+1][j+1]);
}
if (mx == P_LCS[N][M]) {
has_two_lcs = true;
break;
}
idx++;
}
}
if (has_two_lcs) return {-1};
return res;
}
// A, B
// LCS(A, B) = S
//
// i
// LCS1(i-1, j) + LCS2(i+1, j+1)
//
vector<int> ucs(vector<int> A, vector<int> B) {
N = A.size(), M = B.size();
if (A == B) return A;
if (N > 3000 || M > 3000) return {-1};
return lcs(A, B);
}
