Universal Cup Judging System

Universal Cup

时间限制: 1 s 内存限制: 64 MB
统计

给定三个长度为 $n$ 的排列 $a$、$b$ 和 $c$。将排列 $c$ 作用于数组 $a$ 会生成一个满足对所有 $i$ 都有 $d[c[i]] = a[i]$ 的数组 $d$。

在将 $c$ 作用于 $a$ 之前,你可以对排列 $c$ 进行任意次数的操作。在一次操作中,你可以选择两个下标 $i$ 和 $j$,并交换 $c[i]$ 和 $c[j]$。

对于从 $0$ 到 $n$ 的每个 $k$,求出最少需要进行多少次操作,使得将修改后的排列 $c$ 作用于 $a$ 所生成的数组与 $b$ 恰好在 $k$ 个位置上不同,或者判定这是不可能的。

输入格式

第一行包含一个整数 $t$($1 \le t \le 5 \cdot 10^4$),表示测试数据的组数。

每组测试数据的第一行包含一个整数 $n$($1 \le n \le 10^6$)。

接下来的三行分别包含长度为 $n$ 的排列 $a$、$b$ 和 $c$。每个排列都恰好包含从 $1$ 到 $n$ 的每个整数各一次。

所有测试数据中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据,输出 $n + 1$ 个整数,其中第 $k$ 个整数表示为了恰好得到 $k$ 处不同所需的最少操作次数;如果不可能,则输出 $-1$。

样例

输入格式 1

2
3
1 2 3
3 1 2
2 3 1
2
2 1
1 2
1 2

输出格式 1

0 -1 1 2
1 -1 0

说明

在第一组测试数据中,数组为 $a = [1, 2, 3]$。在应用排列 $c = [2, 3, 1]$ 之后,来自第 $1$ 个位置的元素移动到第 $2$ 个位置,第 $2$ 个位置的元素移动到第 $3$ 个位置,第 $3$ 个位置的元素移动到第 $1$ 个位置,最终得到的数组为 $d = [3, 1, 2]$。在这种情况下,它与数组 $b$ 完全一致。因此,$k = 0$ 处不同对应的答案为 $0$ 次操作。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.