Universal Cup Judging System

Universal Cup

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

길이가 $n$인 세 순열 $a$, $b$, $c$가 주어집니다. 배열 $a$에 순열 $c$를 적용하면 모든 $i$에 대해 $d[c[i]] = a[i]$를 만족하는 배열 $d$가 만들어집니다.

$a$에 $c$를 적용하기 전에, 순열 $c$에 연산을 원하는 만큼 수행할 수 있습니다. 한 번의 연산에서 두 인덱스 $i$와 $j$를 선택하여 $c[i]$와 $c[j]$를 교환할 수 있습니다.

$0$부터 $n$까지의 각 $k$에 대해, 수정된 순열 $c$를 $a$에 적용하여 얻은 배열이 $b$와 정확히 $k$개의 위치에서 다르게 되도록 하는 최소 연산 횟수를 구하거나, 그것이 불가능함을 판별하세요.

입력

첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t$ ($1 \le t \le 5 \cdot 10^4$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

다음 세 줄에는 길이가 $n$인 순열 $a$, $b$, $c$가 주어집니다. 각 순열은 $1$부터 $n$까지의 모든 정수를 정확히 한 번씩 포함합니다.

모든 테스트 케이스에 걸친 $n$의 합은 $10^6$을 초과하지 않습니다.

출력

각 테스트 케이스마다 $n + 1$개의 정수를 출력합니다. 그중 $k$번째 정수는 정확히 $k$개의 차이를 얻기 위해 필요한 최소 연산 횟수이며, 불가능한 경우 $-1$입니다.

예제

입력 1

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

출력 1

0 -1 1 2
1 -1 0

참고

첫 번째 테스트 케이스에서 배열은 $a = [1, 2, 3]$입니다. 순열 $c = [2, 3, 1]$을 적용한 후, $1$번째 위치의 원소는 $2$번째로, $2$번째 위치의 원소는 $3$번째로, $3$번째 위치의 원소는 $1$번째로 이동하여 결과 배열은 $d = [3, 1, 2]$가 됩니다. 이 경우 배열 $b$와 일치합니다. 따라서 $k = 0$개의 차이에 대한 답은 $0$번의 연산입니다.

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.