Universal Cup Judging System

Universal Cup

Limite de temps : 1 s Limite de mémoire : 64 MB
Statistiques

Gegeben sind drei Permutationen $a$, $b$ und $c$ der Länge $n$. Das Anwenden der Permutation $c$ auf das Array $a$ erzeugt ein Array $d$, sodass $d[c[i]] = a[i]$ für alle $i$ gilt.

Bevor du $c$ auf $a$ anwendest, darfst du beliebig oft eine Operation auf der Permutation $c$ ausführen. In einer Operation kannst du zwei Indizes $i$ und $j$ wählen und $c[i]$ sowie $c[j]$ vertauschen.

Finde für jedes $k$ von $0$ bis $n$ die minimale Anzahl an Operationen, nach denen das Anwenden der modifizierten Permutation $c$ auf $a$ ein Array erzeugt, das sich von $b$ an genau $k$ Positionen unterscheidet, oder stelle fest, dass dies unmöglich ist.

Eingabe

Die erste Zeile enthält eine ganze Zahl $t$ ($1 \le t \le 5 \cdot 10^4$), die Anzahl der Testfälle.

Die erste Zeile jedes Testfalls enthält eine ganze Zahl $n$ ($1 \le n \le 10^6$).

Die nächsten drei Zeilen enthalten die Permutationen $a$, $b$ und $c$ der Länge $n$. Jede Permutation enthält jede ganze Zahl von $1$ bis $n$ genau einmal.

Die Summe von $n$ über alle Testfälle hinweg überschreitet nicht $10^6$.

Ausgabe

Gib für jeden Testfall $n + 1$ ganze Zahlen aus, wobei die $k$-te davon die minimale Anzahl an Operationen ist, die benötigt wird, um genau $k$ Unterschiede zu erhalten, oder $-1$, falls dies unmöglich ist.

Beispiele

Eingabe 1

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

Ausgabe 1

0 -1 1 2
1 -1 0

Hinweis

Im ersten Testfall lautet das Array $a = [1, 2, 3]$. Nach dem Anwenden der Permutation $c = [2, 3, 1]$ wandert das Element von der $1$. Position an die $2$., von der $2$. an die $3$. und von der $3$. an die $1$., und das resultierende Array ist $d = [3, 1, 2]$. In diesem Fall stimmt es mit dem Array $b$ überein. Daher ist die Antwort für $k = 0$ Unterschiede $0$ Operationen.

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.