Universal Cup Judging System

Universal Cup

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

On vous donne trois permutations $a$, $b$ et $c$ de longueur $n$. Appliquer la permutation $c$ au tableau $a$ produit un tableau $d$ tel que $d[c[i]] = a[i]$ pour tout $i$.

Avant d'appliquer $c$ à $a$, vous pouvez effectuer une opération sur la permutation $c$ autant de fois que vous le souhaitez. En une opération, vous pouvez choisir deux indices $i$ et $j$ et échanger $c[i]$ et $c[j]$.

Pour chaque $k$ de $0$ à $n$, trouvez le nombre minimum d'opérations après lesquelles l'application de la permutation modifiée $c$ à $a$ produit un tableau qui diffère de $b$ en exactement $k$ positions, ou déterminez que c'est impossible.

Entrée

La première ligne contient un entier $t$ ($1 \le t \le 5 \cdot 10^4$), le nombre de cas de test.

La première ligne de chaque cas de test contient un entier $n$ ($1 \le n \le 10^6$).

Les trois lignes suivantes contiennent les permutations $a$, $b$ et $c$ de longueur $n$. Chaque permutation contient chaque entier de $1$ à $n$ exactement une fois.

La somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez $n + 1$ entiers, où le $k$-ième d'entre eux est le nombre minimum d'opérations nécessaires pour obtenir exactement $k$ différences, ou $-1$ si c'est impossible.

Exemples

Entrée 1

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

Sortie 1

0 -1 1 2
1 -1 0

Remarque

Dans le premier cas de test, le tableau est $a = [1, 2, 3]$. Après l'application de la permutation $c = [2, 3, 1]$, l'élément de la $1$-re position se déplace vers la $2$-e, celui de la $2$-e vers la $3$-e, et celui de la $3$-e vers la $1$-re, et le tableau résultant est $d = [3, 1, 2]$. Dans ce cas, il coïncide avec le tableau $b$. Ainsi, la réponse pour $k = 0$ différence est $0$ opération.

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.