Universal Cup Judging System

Universal Cup

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

Du får tre permutationer $a$, $b$ och $c$ av längd $n$. Att tillämpa permutationen $c$ på fältet $a$ ger ett fält $d$ sådant att $d[c[i]] = a[i]$ för alla $i$.

Innan du tillämpar $c$ på $a$ får du utföra en operation på permutationen $c$ valfritt antal gånger. I en operation kan du välja två index $i$ och $j$ och byta plats på $c[i]$ och $c[j]$.

För varje $k$ från $0$ till $n$, hitta det minsta antalet operationer efter vilka tillämpningen av den modifierade permutationen $c$ på $a$ ger ett fält som skiljer sig från $b$ på exakt $k$ positioner, eller avgör att det är omöjligt.

Indata

Den första raden innehåller ett heltal $t$ ($1 \le t \le 5 \cdot 10^4$), antalet testfall.

Den första raden i varje testfall innehåller ett heltal $n$ ($1 \le n \le 10^6$).

De följande tre raderna innehåller permutationerna $a$, $b$ och $c$ av längd $n$. Varje permutation innehåller varje heltal från $1$ till $n$ exakt en gång.

Summan av $n$ över alla testfall överstiger inte $10^6$.

Utdata

För varje testfall, skriv ut $n + 1$ heltal, där det $k$-te av dem är det minsta antalet operationer som krävs för att få exakt $k$ skillnader, eller $-1$ om det är omöjligt.

Exempel

Indata 1

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

Utdata 1

0 -1 1 2
1 -1 0

Förklaring

I det första testfallet är fältet $a = [1, 2, 3]$. Efter att ha tillämpat permutationen $c = [2, 3, 1]$ flyttas elementet från den $1$-sta positionen till den $2$-ndra, från den $2$-ndra till den $3$-dje och från den $3$-dje till den $1$-sta, och det resulterande fältet är $d = [3, 1, 2]$. I detta fall sammanfaller det med fältet $b$. Så svaret för $k = 0$ skillnader är $0$ operationer.

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.