题目链接：Codeforces 1152E

现在 Neko 有一个长度为 $n$ 的数组 $a$ 和一个长度为 $n - 1$ 的排列 $p$。现在他进行如下操作：

• 构造一个长度为 $n - 1$ 的数组 $b$，其中 $b_i = \min(a_i, a_{i +1})$。
• 构造一个长度为 $n - 1$ 的数组 $c$，其中 $c_i = \max(a_i, a_{i +1})$。
• 构造一个长度为 $n - 1$ 的数组 $b'$，其中 $b'_i = b_{p_i}$。
• 构造一个长度为 $n - 1$ 的数组 $b'$，其中 $c'_i = c_{p_i}$。

然而 Neko 只记得数组 $b'$ 和 $c'$ 了，将原来的数组 $a$ 和排列 $p$ 都忘记了。他想让你帮他找到任何一个合法的数组 $a$。如果没有任何一个可能的数组，那么输出 -1。

数据范围：$2 \le n \le 10 ^ 5$，$1 \le b'_i, c'_i \le 10 ^ 9$。

Solution

我们发现，对于 $b_i, c_i$ 一定有 $(a_i, a_{i + 1}) = (b_i, c_i)$ 或 $(a_i, a_{i + 1}) = (c_i, b_i)$，那么考虑 $b, c$ 的置换 $b', c'$，一定有 $(a_{p_i}, a_{p_{i + 1}}) = (b'_i, c'_i)$ 或 $(a_{p_i}, a_{p_{i + 1}}) = (c'_i, b'_i)$。

于是我们构造一张图，连无向边 $(b'_i, c'_i)$，然后在这张图上尝试找到一条欧拉路径（注意不一定是回路），就是最终的答案；否则说明无解。

时间复杂度：$\mathcal O(n \log n)$。

Code

#include <cstdio>
#include <algorithm>
#define fail return printf("-1\n"), 0

const int N = 1e5 + 5, M = 2e5 + 5;

int n, top, b[N], c[N], t[M], p[N], ans[N];
int tot, lnk[N], ter[M], nxt[M], id[M], deg[M];
bool vis[N];

int disc() {
    int tot = 0;
    for (int i = 1; i < n; i++) t[++tot] = b[i], t[++tot] = c[i];
    std::sort(t + 1, t + tot + 1);
    tot = std::unique(t + 1, t + tot + 1) - (t + 1);
    for (int i = 1; i < n; i++) {
        b[i] = std::lower_bound(t + 1, t + tot + 1, b[i]) - t;
        c[i] = std::lower_bound(t + 1, t + tot + 1, c[i]) - t;
    }
    return tot;
}
void addEdge(int u, int v, int x) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, id[tot] = x;
}
void dfs(int u) {
    for (int &i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i], x = id[i];
        if (vis[x]) continue;
        vis[x] = true, dfs(v);
    }
    ans[++top] = u;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) scanf("%d", &b[i]);
    for (int i = 1; i < n; i++) scanf("%d", &c[i]);
    for (int i = 1; i < n; i++) if (b[i] > c[i]) fail;
    int k = disc();
    for (int i = 1; i < n; i++) {
        addEdge(b[i], c[i], i);
        addEdge(c[i], b[i], i);
        deg[b[i]]++, deg[c[i]]++;
    }
    int cnt = 0;
    for (int i = 1; i <= k; i++) if (deg[i] & 1) p[++cnt] = i;
    if (cnt > 2) fail;
    dfs(cnt ? p[1] : 1);
    if (top < n) fail;
    for (int i = top; i >= 1; i--) {
        printf("%d%c", t[ans[i]], " \n"[i == 1]);
    }
    return 0;
}