Universal Cup Judging System

Universal Cup

Límite de tiempo: 1 s Límite de memoria: 64 MB
Estadísticas

Dane są trzy permutacje $a$, $b$ oraz $c$ długości $n$. Zastosowanie permutacji $c$ do tablicy $a$ daje tablicę $d$ taką, że $d[c[i]] = a[i]$ dla każdego $i$.

Przed zastosowaniem $c$ do $a$ możesz wykonać operację na permutacji $c$ dowolną liczbę razy. W jednej operacji możesz wybrać dwa indeksy $i$ oraz $j$ i zamienić miejscami $c[i]$ oraz $c[j]$.

Dla każdego $k$ od $0$ do $n$ znajdź minimalną liczbę operacji, po których zastosowanie zmodyfikowanej permutacji $c$ do $a$ daje tablicę różniącą się od $b$ na dokładnie $k$ pozycjach, lub stwierdź, że jest to niemożliwe.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \le t \le 5 \cdot 10^4$), oznaczającą liczbę przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera liczbę całkowitą $n$ ($1 \le n \le 10^6$).

Kolejne trzy wiersze zawierają permutacje $a$, $b$ oraz $c$ długości $n$. Każda permutacja zawiera każdą liczbę całkowitą od $1$ do $n$ dokładnie raz.

Suma $n$ po wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz $n + 1$ liczb całkowitych, gdzie $k$-ta z nich to minimalna liczba operacji potrzebnych do uzyskania dokładnie $k$ różnic, lub $-1$, jeśli jest to niemożliwe.

Przykład

Wejście 1

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

Wyjście 1

0 -1 1 2
1 -1 0

Uwagi

W pierwszym przypadku testowym tablica to $a = [1, 2, 3]$. Po zastosowaniu permutacji $c = [2, 3, 1]$ element z $1$. pozycji przechodzi na $2$., z $2$. na $3$., a z $3$. na $1$., w wyniku czego powstaje tablica $d = [3, 1, 2]$. W tym przypadku pokrywa się ona z tablicą $b$. Zatem odpowiedź dla $k = 0$ różnic wynosi $0$ operacji.

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.