Universal Cup Judging System

Universal Cup

시간 제한: 1 s 메모리 제한: 64 MB
통계

Se te dan tres permutaciones $a$, $b$ y $c$ de longitud $n$. Aplicar la permutación $c$ al arreglo $a$ produce un arreglo $d$ tal que $d[c[i]] = a[i]$ para todo $i$.

Antes de aplicar $c$ a $a$, puedes realizar una operación sobre la permutación $c$ cualquier número de veces. En una operación, puedes elegir dos índices $i$ y $j$ e intercambiar $c[i]$ y $c[j]$.

Para cada $k$ desde $0$ hasta $n$, encuentra el número mínimo de operaciones tras las cuales aplicar la permutación modificada $c$ a $a$ produce un arreglo que difiere de $b$ en exactamente $k$ posiciones, o determina que es imposible.

Entrada

La primera línea contiene un entero $t$ ($1 \le t \le 5 \cdot 10^4$), el número de casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ ($1 \le n \le 10^6$).

Las siguientes tres líneas contienen las permutaciones $a$, $b$ y $c$ de longitud $n$. Cada permutación contiene cada entero desde $1$ hasta $n$ exactamente una vez.

La suma de $n$ en todos los casos de prueba no supera $10^6$.

Salida

Para cada caso de prueba, imprime $n + 1$ enteros, donde el $k$-ésimo de ellos es el número mínimo de operaciones necesarias para obtener exactamente $k$ diferencias, o $-1$ si es imposible.

Ejemplos

Entrada 1

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

Salida 1

0 -1 1 2
1 -1 0

Nota

En el primer caso de prueba, el arreglo es $a = [1, 2, 3]$. Después de aplicar la permutación $c = [2, 3, 1]$, el elemento de la $1$-ª posición se mueve a la $2$-ª, de la $2$-ª a la $3$-ª y de la $3$-ª a la $1$-ª, y el arreglo resultante es $d = [3, 1, 2]$. En este caso, coincide con el arreglo $b$. Por lo tanto, la respuesta para $k = 0$ diferencias es $0$ operaciones.

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.