Particija

시간 제한1초메모리 제한2048 MB

요약

집합 {1,...,N}의 두 분할이 주어질 때, 두 분할의 블록만으로 {1,...,N}을 다시 분할하는 최소 블록 수를 구하고, 라벨 하나를 바꿔 이 값을 최소화하거나 최대화한다.

난이도: 어려움10점 중 8점
유형: 유니온 파인드, 그래프, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

Particija skupa $\\{1, 2, \dots , N\\}$ (za neki zadani prirodni broj $N$ ) je bilo koja kolekcija nepraznih skupova takvih da se svaki broj od $1$ do $N$ pojavljuje u točno jednom od tih skupova. Na primjer, jednu particiju skupa $\\{1, 2, 3, 4, 5\\}$ čine skupovi $\\{1, 3\\}$ , $\\{2, 4\\}$ i $\\{5\\}$ . Jedan način na koji možemo zadati particiju je koristeći niz brojeva $x\_1, x\_2, \dots , x\_N$ ( $1 ≤ x\_i ≤ N$ ) tako da proglasimo da se $i$ i $j$ nalaze u istom skupu particije ako i samo ako vrijedi da je $x\_i = x\_j$ . Particiju iz prethodnog primjera mogli smo zadati nizom $1, 2, 1, 2, 3$ , ali također i nizom poput $5, 1, 5, 1, 4$ .

Patricija je djevojka koja u svom vlasništvu ima dvije particije skupa $\\{1, 2, \dots , N\\}$ . Prva od tih particija zadana je nizom $a\_1, a\_2, \dots , a\_N$ , a druga nizom $b\_1, b\_2, \dots , b\_N$ . Patriciju zanima odgovor na sljedeće pitanje: koji je najmanji broj skupova koji tvore particiju skupa $\\{1, 2, \dots , N\\}$ , ako na raspolaganju ima skupove navedenih dviju particija.

U ovisnosti o zadanom broju $k ∈ \\{0, 1, 2\\}$ potrebno je napraviti sljedeće.

Ako je $k = 0$ , potrebno je pronaći odgovor na Patricijino pitanje.
Ako je $k = 1$ , dozvoljeno je promijeniti najviše jedan od danih $2N$ brojeva koji određuju particije. Potrebno je pronaći najmanji mogući odgovor na Patricijino pitanje nakon najviše jedne promjene. Drugim riječima, potrebno je minimizirati najmanji broj skupova koji tvore particiju.
Ako je $k = 2$ , dozvoljeno je promijeniti najviše jedan od danih $2N$ brojeva koji određuju particije. Potrebno je pronaći najveći mogući odgovor na Patricijino pitanje nakon najviše jedne promjene. Drugim riječima, potrebno je maksimizirati najmanji broj skupova koji tvore particiju.

Napomenimo da kada je $k = 1$ ili $k = 2$ , nova vrijednost promijenjenog broja mora biti između $1$ i $N$ .

Pomozite Patriciji te napravite program koji rješava $T$ ovakvih test primjera.

입력

U prvom su retku brojevi $T$ i $k$ , redom broj test primjera te parametar koji određuje vrstu zadatka.

Slijede opisi $T$ test primjera.

Svaki test primjer započinje prirodnim brojem $N$ , veličinom particije.

U sljedeća dva retka nalaze se nizovi $a\_1, \dots , a\_N$ te $b\_1, \dots , b\_N$ koji određuju particije.

출력

Za svaki od $T$ test primjera u zasebni redak ispišite odgovor na traženo pitanje.

힌트

Pojašnjenje prvog probnog primjera:

Za prvi test primjer: Prvi niz određuje particiju na skupove $\\{1, 2\\}$ , $\\{3\\}$ i $\\{4\\}$ , a drugi na skupove $\\{1\\}$ , $\\{2\\}$ i $\\{3, 4\\}$ . Koristeći te skupove možemo napraviti particiju na dva skupa $\\{1, 2\\}$ i $\\{3, 4\\}$ .

Za drugi test primjer: Prvi niz određuje particiju na skupove $\\{1, 2, 3, 4\\}$ , $\\{5\\}$ , $\\{6\\}$ i $\\{7\\}$ , a drugi na skupove $\\{1\\}$ , $\\{2\\}$ , $\\{3\\}$ i $\\{4, 5, 6, 7\\}$ . Bilo koja od tih particija ujedno je i optimalna.

예제3

예제 1

입력

2 0
4
1 1 2 3
1 2 3 3
7
1 1 1 1 2 3 4
1 2 3 4 4 4 4

예상 출력

2
4

예제 2

입력

3 1
4
1 1 2 3
1 2 3 3
4
1 1 1 1
1 2 3 3
7
1 1 1 1 2 3 4
1 2 3 4 4 4 4

예상 출력

2
1
2

예제 3

입력

3 2
4
1 1 2 3
1 2 3 3
4
1 1 1 3
1 2 3 3
7
1 1 1 2 3 4 5
1 2 3 4 4 4 4

예상 출력

3
3
4