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

点击量：116

这种找可行解的问题套路还是比较多的。

目录

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]$

题解：

对于 $b_i=\min(a_i,a_{i+1})$ 和 $c_i=\max(a_i,a_{i+1})$ 这两个函数，取值一定在 $a_i$ 和 $a_{i+1}​$ 这两个值中。

当 $a_i= a_{i+1}$ 时，$b_i=c_i=a_i$；当 $a_i\ne a_{i+1}$ 时，$b_i=a_i,c_i=a_{i+1}$ 或 $b_i=a_{i+1},c=a_i$。

我们对它们进行匹配，在 $b_i$ 和 $c_i$ 之间连有向边。如果 $b_i\to c_i$，说明 $b_i=a_i,c_i=a_{i+1}$，否则将 $b_i$ 和 $c_i$ 换过来。

根据取值，在 $b_i,c_i$ 与 $b_{i+1},c_{i+1}$ 中一定有一对相同元素，所以在序列的相邻位置会有联系。因此 $b_i,c_i,b_{i+1},c_{i+1}$ 实际上是 3 个点，它们由两条边相连。

每给出一对 $b_i,c_i$，我们就知道了一条这样的边。对于 $n$ 对这样的信息，我们就需要 $n$ 个点，$n-1$ 条边来把它们串成一个序列，并且数字的重复出现互不影响。

这就很容易联想到欧拉路了，在 $b_i$ 和 $c_i$ 之间连一条无向边。在求欧拉路的过程中需要用到类似当前弧优化的操作，可以把欧拉路做到 $O(n)$。

加上离散化的复杂度，这道题可以在 $O(n\log n)$ 的时间复杂度内完成。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    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 head[100100],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int b[100100],c[100100],r[200100],d[100100];
int stk[200100],tp=0,cnt=0;
void dfs(int x)
{
    int i=head[x];
    while(~i)
    {
        ++cnt;
        head[x]=e[i].nxt;
        if(!e[i].used)
        {
            e[i].used=1;
            e[i^1].used=1;
            dfs(e[i].n);
        }
        i=head[x];
    }
    stk[++tp]=x;
}
int main()
{
    memset(head,-1,sizeof(head));
    int n=read();
    for(int i=1;i<n;++i)
    {
        b[i]=read();
        r[i]=b[i];
    }
    for(int i=1;i<n;++i)
    {
        c[i]=read();
        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;
        add(b[i],c[i]);
        ++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;
}