#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> I = {-1};
struct indexes{
vector<int> A[200002], B[200002], C, D, E;
int F[200002];
bool is_sq(int a, int b, int c, int d){
return A[a][c-1] < A[b][A[b].size()-d] && B[a][c-1] < B[b][B[b].size()-d];
}
bool init(vector<int> a, vector<int> b){
for(int i = 0; i < a.size(); i++)A[a[i]].push_back(i);
for(int i = 0; i < b.size(); i++)B[b[i]].push_back(i);
C.clear(), D.clear(), E.clear();
for(int i:a)if(A[i].size() <= B[i].size())C.push_back(i);
for(int i:b)if(A[i].size() >= B[i].size())D.push_back(i);
int N = C.size();
int M = D.size();
int x = 0, y = 0;
while(x < N || y < M){
if(x || y)F[E[E.size()-1]]++;
if(x == N){
E.push_back(D[y++]);
continue;
}
if(y == M){
E.push_back(C[x++]);
continue;
}
if(A[C[x]].size() == B[C[x]].size() || A[D[y]].size() == B[D[y]].size()){
if(C[x] == D[y]){
E.push_back(D[y++]);
x++;
continue;
}
if(A[C[x]].size() != B[C[x]].size()){
E.push_back(C[x++]);
continue;
}
if(A[D[y]].size() != B[D[y]].size()){
E.push_back(D[y++]);
continue;
}
return true;
}
bool X = is_sq(C[x], D[y], F[C[x]]+1, B[D[y]].size()-F[D[y]]), Y = is_sq(D[y], C[x], F[D[y]]+1, A[C[x]].size()-F[C[x]]);
if(X && Y)return true;
if(Y){
E.push_back(D[y++]);
continue;
}
if(X){
E.push_back(C[x++]);
continue;
}
return true;
}
return false;
}
} H;
vector<int> ucs(vector<int> A, vector<int> B) {
int N = A.size(), M = B.size();
if(H.init(A, B))return I;
return H.E;
}
