Universal Cup Judging System

Universal Cup

時間限制: 1 s 記憶體限制: 64 MB
统计

Sinulle annetaan kolme pituutta $n$ olevaa permutaatiota $a$, $b$ ja $c$. Permutaation $c$ soveltaminen taulukkoon $a$ tuottaa taulukon $d$, jolle pätee $d[c[i]] = a[i]$ kaikilla $i$.

Ennen kuin sovellat permutaatiota $c$ taulukkoon $a$, voit suorittaa permutaatiolle $c$ operaation mielivaltaisen monta kertaa. Yhdessä operaatiossa voit valita kaksi indeksiä $i$ ja $j$ ja vaihtaa alkiot $c[i]$ ja $c[j]$ keskenään.

Etsi jokaiselle $k$ väliltä $0$:sta $n$:ään pienin määrä operaatioita, joiden jälkeen muokatun permutaation $c$ soveltaminen taulukkoon $a$ tuottaa taulukon, joka eroaa taulukosta $b$ täsmälleen $k$ kohdassa, tai päätä, että se on mahdotonta.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $t$ ($1 \le t \le 5 \cdot 10^4$), testitapausten lukumäärän.

Kunkin testitapauksen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^6$).

Seuraavat kolme riviä sisältävät pituutta $n$ olevat permutaatiot $a$, $b$ ja $c$. Jokainen permutaatio sisältää jokaisen kokonaisluvun väliltä $1$:stä $n$:ään täsmälleen kerran.

Lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^6$.

Tuloste

Tulosta jokaiselle testitapaukselle $n + 1$ kokonaislukua, joista $k$:s on pienin tarvittava operaatioiden määrä täsmälleen $k$ eron saamiseksi, tai $-1$, jos se on mahdotonta.

Esimerkit

Syöte 1

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

Tuloste 1

0 -1 1 2
1 -1 0

Huomautus

Ensimmäisessä testitapauksessa taulukko on $a = [1, 2, 3]$. Permutaation $c = [2, 3, 1]$ soveltamisen jälkeen alkio $1$. sijainnista siirtyy $2$. sijaintiin, $2$. sijainnista $3$. sijaintiin ja $3$. sijainnista $1$. sijaintiin, ja tuloksena saatava taulukko on $d = [3, 1, 2]$. Tässä tapauksessa se on sama kuin taulukko $b$. Siispä vastaus $k = 0$ erolle on $0$ operaatiota.

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.