#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
// Check if sequence 'small' is a subsequence of 'large'
bool is_subsequence(const vector<int>& large, const vector<int>& small) {
int j = 0;
for (int i = 0; i < (int)large.size() && j < (int)small.size(); ++i) {
if (large[i] == small[j]) j++;
}
return j == (int)small.size();
}
vector<int> ucs(vector<int> A, vector<int> B) {
unordered_map<int, queue<int>> pos_in_B;
for (int i = 0; i < (int)B.size(); ++i) {
pos_in_B[B[i]].push(i);
}
vector<int> result;
int last_pos = -1;
for (int i = 0; i < (int)A.size(); ++i) {
int val = A[i];
if (pos_in_B.count(val)) {
while (!pos_in_B[val].empty() && pos_in_B[val].front() <= last_pos) {
pos_in_B[val].pop();
}
if (!pos_in_B[val].empty()) {
last_pos = pos_in_B[val].front();
pos_in_B[val].pop();
result.push_back(val);
}
}
}
if (result.empty()) return {}; // empty sequence is valid UCS
unordered_map<int, queue<int>> pos_in_A;
for (int i = 0; i < (int)A.size(); ++i) {
pos_in_A[A[i]].push(i);
}
vector<int> alt_result;
last_pos = -1;
for (int i = 0; i < (int)B.size(); ++i) {
int val = B[i];
if (pos_in_A.count(val)) {
while (!pos_in_A[val].empty() && pos_in_A[val].front() <= last_pos) {
pos_in_A[val].pop();
}
if (!pos_in_A[val].empty()) {
last_pos = pos_in_A[val].front();
pos_in_A[val].pop();
alt_result.push_back(val);
}
}
}
if (alt_result != result &&
(!is_subsequence(result, alt_result) || !is_subsequence(alt_result, result))) {
return {-1}; // no unique UCS
}
return result;
}
