A permutation of length $k$ is a sequence of $k$ integers from $1$ to $k$ containing each integer exactly once. For example, the sequence $[3, 1, 2]$ is a permutation of length $3$.

When Neko was five, he thought of an array $a$ of $n$ positive integers and a permutation $p$ of length $n - 1$. Then, he performed the following:

  Constructed an array $b$ of length $n-1$, where $b_i = \min(a_i, a_{i+1})$.  Constructed an array $c$ of length $n-1$, where $c_i = \max(a_i, a_{i+1})$.  Constructed an array $b'$ of length $n-1$, where $b'_i = b_{p_i}$.  Constructed an array $c'$ of length $n-1$, where $c'_i = c_{p_i}$. 

For example, if the array $a$ was $[3, 4, 6, 5, 7]$ and permutation $p$ was $[2, 4, 1, 3]$, then Neko would have constructed the following arrays:

  $b = [3, 4, 5, 5]$  $c = [4, 6, 6, 7]$  $b' = [4, 5, 3, 5]$  $c' = [6, 7, 4, 6]$ 

Then, he wrote two arrays $b'$ and $c'$ on a piece of paper and forgot about it. 14 years later, when he was cleaning up his room, he discovered this old piece of paper with two arrays $b'$ and $c'$ written on it. However he can't remember the array $a$ and permutation $p$ he used.

In case Neko made a mistake and there is no array $a$ and permutation $p$ resulting in such $b'$ and $c'$, print -1. Otherwise, help him recover any possible array $a$. 


-----Input-----

The first line contains an integer $n$ ($2 \leq n \leq 10^5$) — the number of elements in array $a$.

The second line contains $n-1$ integers $b'_1, b'_2, \ldots, b'_{n-1}$ ($1 \leq b'_i \leq 10^9$).

The third line contains $n-1$ integers $c'_1, c'_2, \ldots, c'_{n-1}$ ($1 \leq c'_i \leq 10^9$).


-----Output-----

If Neko made a mistake and there is no array $a$ and a permutation $p$ leading to the $b'$ and $c'$, print -1. Otherwise, print $n$ positive integers $a_i$ ($1 \le a_i \le 10^9$), denoting the elements of the array $a$.

If there are multiple possible solutions, print any of them. 


-----Examples-----
Input
5
4 5 3 5
6 7 4 6

Output
3 4 6 5 7 

Input
3
2 4
3 2

Output
-1

Input
8
2 3 1 1 2 4 3
3 4 4 2 5 5 4

Output
3 4 5 2 1 4 3 2 



-----Note-----

The first example is explained is the problem statement.

In the third example, for $a = [3, 4, 5, 2, 1, 4, 3, 2]$, a possible permutation $p$ is $[7, 1, 5, 4, 3, 2, 6]$. In that case, Neko would have constructed the following arrays:

  $b = [3, 4, 2, 1, 1, 3, 2]$  $c = [4, 5, 5, 2, 4, 4, 3]$  $b' = [2, 3, 1, 1, 2, 4, 3]$  $c' = [3, 4, 4, 2, 5, 5, 4]$

Difficulty: interview

Starter code:

Solutions:
from collections import defaultdict, Counter
N = int(input())
B = list(map(int, input().split()))
C = list(map(int, input().split()))
Edge = defaultdict(list)
Edc = defaultdict(int)
for b, c in zip(B, C):
    if b > c:
        print(-1)
        return
    Edge[b].append(c)
    Edc[(b, c)] += 1
    if b != c:
        Edge[c].append(b)
Deg = Counter(B + C)
eul = 0
st = []
for k, v in list(Deg.items()):
    if v % 2:
        eul += 1
        st.append(k)
s, e = B[0], B[0]
if eul and eul != 2:
    print(-1)
    return
if eul:
    s, e = st[0], st[1]
ans = [s]
while True:
    vn = ans[-1]
    while True:
        vf = Edge[vn][-1]
        if Deg[vf] != 0 and Edc[(vn, vf) if vn < vf else (vf, vn)]:
            break
        Edge[vn].pop()
    vf = Edge[vn].pop()
    Deg[vn] -= 1
    Deg[vf] -= 1
    Edc[(vn, vf) if vn < vf else (vf, vn)] -= 1
    ans.append(vf)
    if not Deg[vf]:
        break
loop = defaultdict(list)
for a in ans:
    if Deg[a]:
        loopa = [a]
        while Deg[a]:
            vn = loopa[-1]
            while True:
                vf = Edge[vn][-1]
                if Deg[vf] != 0 and Edc[(vn, vf) if vn < vf else (vf, vn)]:
                    break
                Edge[vn].pop()
            vf = Edge[vn].pop()
            Deg[vn] -= 1
            Deg[vf] -= 1
            Edc[(vn, vf) if vn < vf else (vf, vn)] -= 1
            loopa.append(vf)
            if not Deg[vf]:
                break
        loop[a] = loopa
Ans = [] 
for a in ans:
    if loop[a]:
        Ans.extend(loop[a])
        loop[a] = []
    else:
        Ans.append(a)    
if len(Ans) != N:
    print(-1)
    return
print(*Ans)