#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int INF = 1e9;
const int MAXV = 200000;
struct SegTree {
vector<int> tree;
SegTree() {
tree.assign(4 * MAXV + 100, INF);
}
void update(int node, int start, int end, int idx, int val) {
if(start == end) {
tree[node] = val;
return;
}
int mid = (start + end) / 2;
if(idx <= mid) update(2 * node, start, mid, idx, val);
else update(2 * node + 1, mid + 1, end, idx, val);
tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
int query_all() {
return tree[1];
}
};
vector<int> posA[MAXV + 5];
vector<int> posB[MAXV + 5];
int ptrA[MAXV + 5];
int ptrB[MAXV + 5];
int k_val[MAXV + 5];
bool is_cand[MAXV + 5];
bool in_affected[MAXV + 5];
inline int nextA(int y) {
if (ptrA[y] < posA[y].size()) return posA[y][ptrA[y]];
return INF;
}
inline int nextB(int y) {
if (ptrB[y] < posB[y].size()) return posB[y][ptrB[y]];
return INF;
}
vector<int> ucs(vector<int> A, vector<int> B) {
int n = A.size();
int m = B.size();
for(int i = 0; i <= MAXV; ++i) {
posA[i].clear(); posB[i].clear();
ptrA[i] = 0; ptrB[i] = 0;
k_val[i] = 0;
is_cand[i] = false;
in_affected[i] = false;
}
for(int i = 0; i < n; ++i) posA[A[i]].push_back(i);
for(int j = 0; j < m; ++j) posB[B[j]].push_back(j);
long long L = 0;
SegTree stA, stB;
for(int x = 0; x <= MAXV; ++x) {
k_val[x] = min(posA[x].size(), posB[x].size());
L += k_val[x];
if (k_val[x] > 0) {
stA.update(1, 0, MAXV, x, posA[x][posA[x].size() - k_val[x]]);
stB.update(1, 0, MAXV, x, posB[x][posB[x].size() - k_val[x]]);
}
}
if (L == 0) return {};
int limitA = min(stA.query_all(), n - 1);
int limitB = min(stB.query_all(), m - 1);
vector<int> affected;
auto add_affected = [&](int y) {
if (!in_affected[y]) {
affected.push_back(y);
in_affected[y] = true;
}
};
for(int i = 0; i <= limitA; ++i) {
if (nextA(A[i]) == i) add_affected(A[i]);
}
for(int j = 0; j <= limitB; ++j) {
if (nextB(B[j]) == j) add_affected(B[j]);
}
int num_cands = 0;
vector<int> cand_list;
auto check = [&](int y) {
bool valid = (k_val[y] > 0) && (nextA(y) <= limitA) && (nextB(y) <= limitB);
if (valid != is_cand[y]) {
is_cand[y] = valid;
if (valid) {
num_cands++;
cand_list.push_back(y);
} else {
num_cands--;
}
}
};
for(int y : affected) check(y);
for(int y : affected) in_affected[y] = false;
affected.clear();
auto get_cand = [&]() {
while(!cand_list.empty()) {
int y = cand_list.back();
if (is_cand[y]) return y;
cand_list.pop_back();
}
return -1;
};
vector<int> U;
int pA = 0, pB = 0;
int old_limitA = limitA, old_limitB = limitB;
while(L > 0) {
// 如果备选项不为唯一的1个，说明不存在一个最全且唯一的公共子序列
if (num_cands != 1) return {-1};
int x = get_cand();
U.push_back(x);
int new_pA = nextA(x) + 1;
int new_pB = nextB(x) + 1;
k_val[x]--;
L--;
if (k_val[x] == 0) {
stA.update(1, 0, MAXV, x, INF);
stB.update(1, 0, MAXV, x, INF);
} else {
stA.update(1, 0, MAXV, x, posA[x][posA[x].size() - k_val[x]]);
stB.update(1, 0, MAXV, x, posB[x][posB[x].size() - k_val[x]]);
}
limitA = min(stA.query_all(), n - 1);
limitB = min(stB.query_all(), m - 1);
// 扫过跳过且无效的记录
for(int i = pA; i < new_pA; ++i) {
if (nextA(A[i]) == i) { ptrA[A[i]]++; add_affected(A[i]); }
}
for(int j = pB; j < new_pB; ++j) {
if (nextB(B[j]) == j) { ptrB[B[j]]++; add_affected(B[j]); }
}
// 扫描由于限值上限拉大而新落入区间的可行记录
for(int i = max(new_pA, old_limitA + 1); i <= limitA; ++i) {
if (nextA(A[i]) == i) add_affected(A[i]);
}
for(int j = max(new_pB, old_limitB + 1); j <= limitB; ++j) {
if (nextB(B[j]) == j) add_affected(B[j]);
}
pA = new_pA; pB = new_pB;
old_limitA = limitA; old_limitB = limitB;
for(int y : affected) check(y);
for(int y : affected) in_affected[y] = false;
affected.clear();
}
return U;
}
