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.