Universal Cup Judging System

Universal Cup

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

長さ $n$ の 3 つの順列 $a$, $b$, $c$ が与えられます。順列 $c$ を配列 $a$ に適用すると、すべての $i$ に対して $d[c[i]] = a[i]$ を満たす配列 $d$ が得られます。

$c$ を $a$ に適用する前に、順列 $c$ に対して操作を何回でも行うことができます。1 回の操作では、2 つの添字 $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$) が与えられます。

続く 3 行には、長さ $n$ の順列 $a$, $b$, $c$ が与えられます。各順列は $1$ から $n$ までのすべての整数をちょうど 1 回ずつ含みます。

すべてのテストケースにわたる $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.