# CF1152E Neko and Flashback 题解【欧拉路】【构造】

## Description

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\le n\le 10^5)$ — the number of elements in array $a$.

The second line contains $n-1$ integers $b′_1,b′_2,\dots,b′_{n−1}(1\le b′_i\le 10^9)$.

The third line contains $n-1$ integers $c′_1,c′_2,\dots,c′_{n−1}(1\le c′_i\le 10^9)$.

## Output

If Neko made a mistake and there is no array aa 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]$

## Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
{
x=x*10+(ch&15);
ch=getchar();
}
return x;
}
struct edge
{
int n,nxt;
bool used;
edge(int n,int nxt)
{
this->n=n;
this->nxt=nxt;
used=0;
}
edge(){}
}e[200100];
{
}
int b[100100],c[100100],r[200100],d[100100];
int stk[200100],tp=0,cnt=0;
void dfs(int x)
{
while(~i)
{
++cnt;
if(!e[i].used)
{
e[i].used=1;
e[i^1].used=1;
dfs(e[i].n);
}
}
stk[++tp]=x;
}
int main()
{
for(int i=1;i<n;++i)
{
r[i]=b[i];
}
for(int i=1;i<n;++i)
{
if(c[i]<b[i])
{
puts("-1");
return 0;
}
r[n+i-1]=c[i];
}
sort(r+1,r+2*n-1);
int m=unique(r+1,r+2*n-1)-r-1;
for(int i=1;i<n;++i)
{
b[i]=lower_bound(r+1,r+m+1,b[i])-r;
c[i]=lower_bound(r+1,r+m+1,c[i])-r;
++d[b[i]];
++d[c[i]];
}
int s=1,flag=0;
for(int i=1;i<=m;++i)
if(d[i]&1)
{
++flag;
s=i;
}
if(flag>2)
{
puts("-1");
return 0;
}
dfs(s);
if(tp!=n)
puts("-1");
else
for(int i=1;i<=tp;++i)
printf("%d ",r[stk[i]]);
return 0;
}


Subscribe

/* */