#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> ucs(vector<int> A, vector<int> B) {
int N = A.size(), M = B.size();
vector<int> prev(M + 1), curr(M + 1);
// Build only 2 rows of DP
for (int i = N - 1; i >= 0; --i) {
curr.assign(M + 1, 0);
for (int j = M - 1; j >= 0; --j) {
if (A[i] == B[j]) {
curr[j] = 1 + prev[j + 1];
} else {
curr[j] = max(prev[j], curr[j + 1]);
}
}
swap(curr, prev);
}
// Backtrack while checking for multiple choices
vector<int> res;
int i = 0, j = 0;
while (i < N && j < M) {
if (A[i] == B[j]) {
res.push_back(A[i]);
i++;
j++;
} else {
int skipA = (i + 1 <= N) ? prev[j] : 0;
int skipB = (j + 1 <= M) ? prev[j + 1] : 0;
int best = max(skipA, skipB);
// We must recompute current dp[i][j+1] since it's not stored
int currJ = 0;
if (j + 1 < M) {
if (A[i] == B[j + 1]) currJ = 1 + prev[j + 2];
else currJ = max(prev[j + 1], 0);
}
// Detect multiple choices
int cnt = 0;
if (skipA == best) cnt++;
if (currJ == best) cnt++;
if (cnt > 1) return {-1};
if (skipA == best) i++;
else j++;
}
// Update prev row manually
for (int jj = M - 1; jj >= 0; --jj) {
if (A[i] == B[jj]) {
curr[jj] = 1 + prev[jj + 1];
} else {
curr[jj] = max(prev[jj], curr[jj + 1]);
}
}
swap(prev, curr);
}
return res;
}
