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: VERY_HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Starter code:

Solutions:
class multiset:

	def __init__(self):
		self.items = dict()
		self.len = 0

	def add(self, it):
		self.items[it] = self.items.get(it, 0) + 1
		self.len += 1

	def remove(self, it):
		it_value = self.items.get(it, 1) - 1
		if it_value == 0:
			self.items.__delitem__(it)
		else:
			self.items[it] = it_value
		self.len -= 1

	def pop(self):
		it = next(iter(self.items.keys()))
		self.remove(it)
		return it

	def __len__(self):
		return self.len

	def __str__(self):
		return str(self.items)
import sys
fd = sys.stdin
n = int(fd.readline())
bp = [int(i) for i in fd.readline().split()]
cp = [int(i) for i in fd.readline().split()]
for i in range(n - 1):
	if bp[i] > cp[i]:
		print(-1)
		sys.exit()
map_value = dict()
count = 0
for i in bp + cp:
	if i not in map_value:
		map_value[i] = count
		count += 1
E = [multiset() for i in range(count)]
for i in range(n - 1):
	(a, b) = (map_value[bp[i]], map_value[cp[i]])
	E[a].add(b)
	E[b].add(a)
odd_vert = []
for i in range(count):
	if len(E[i]) % 2 == 1:
		odd_vert.append(i)
first_vert = 0
if len(odd_vert) == 2:
	first_vert = count
	E.append(multiset())
	E[count].add(odd_vert[0])
	E[odd_vert[0]].add(count)
	E[count].add(odd_vert[1])
	E[odd_vert[1]].add(count)
elif len(odd_vert) != 0:
	print(-1)
	sys.exit()
stack = [first_vert]
sol = []
while stack:
	v = stack[-1]
	if len(E[v]) == 0:
		sol.append(v)
		stack.pop()
	else:
		u = E[v].pop()
		E[u].remove(v)
		stack.append(u)
inv_map_value = {v: i for (i, v) in map_value.items()}
if sol[0] == count and len(sol) != n + 2:
	print(-1)
elif sol[0] == count:
	for i in range(1, len(sol) - 1):
		print(inv_map_value[sol[i]])
elif len(sol) != n:
	print(-1)
else:
	for i in sol:
		print(inv_map_value[i])


class multiset:

	def __init__(self):
		self.contenido = dict()
		self.len = 0

	def add(self, x):
		self.contenido[x] = self.contenido.get(x, 0) + 1
		self.len += 1

	def remove(self, x):
		valor = self.contenido.get(x, 1) - 1
		if valor == 0:
			del self.contenido[x]
		else:
			self.contenido[x] = valor
		self.len -= 1

	def pop(self):
		x = next(iter(self.contenido.keys()))
		self.remove(x)
		return x

	def __len__(self):
		return self.len

	def __str__(self):
		return str(self.contenido)
n = int(input())
b = [int(a) for a in input().split()]
c = [int(a) for a in input().split()]
for (x, y) in zip(b, c):
	if x > y:
		print(-1)
		exit()
trad = dict()
contador = 0
for a in b + c:
	if not a in trad:
		trad[a] = contador
		contador += 1
v = [multiset() for _ in range(contador)]
auxb = [trad[a] for a in b]
auxc = [trad[a] for a in c]
for (x, y) in zip(auxb, auxc):
	v[x].add(y)
	v[y].add(x)
impares = []
for (i, a) in enumerate(v):
	if len(a) % 2:
		impares.append(i)
primero = 0
if len(impares) == 2:
	primero = impares[0]
elif len(impares) != 0:
	print(-1)
	exit()
stack = [primero]
sol = []
while len(stack):
	p = stack[-1]
	if len(v[p]) == 0:
		sol.append(p)
		stack.pop()
	else:
		h = v[p].pop()
		v[h].remove(p)
		stack.append(h)
tradaux = {v: k for (k, v) in trad.items()}
if len(sol) != n:
	print(-1)
	exit()
for i in sol:
	print(tradaux[i])


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)