Universal Cup Judging System

Universal Cup

Time Limit: 1 s Memory Limit: 64 MB
Statistics

Сізге ұзындығы $n$ болатын үш $a$, $b$ және $c$ орын алмастыруы берілген. $a$ массивіне $c$ орын алмастыруын қолдану барлық $i$ үшін $d[c[i]] = a[i]$ орындалатындай $d$ массивін береді.

$c$ орын алмастыруын $a$-ға қолданбас бұрын, сіз $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.