Državno natjecanje 2019. / Osnovna škola (8. razred) - 3. zadatak

Mirko je na papiru pronašao dva niza od N prirodnih brojeva.

Budući da jako voli pravilnosti odlučio ih je učiniti jednakima. Pored pravilnosti Mirko voli i mađioničarske trikove.

Odmalena posjeduje magične sposobnosti koje ni sam ne razumije.

Jedino što zna je da ako desnom rukom pokrije jedan broj u prvom nizu, a lijevom rukom pokrije jedan broj u drugom nizu te izgovori čarobne riječi ta dva broja se zamijene.

Svakom upotrebom magije on gubi čarobnu energiju.

Zato moli tebe da mu pomogneš pronaći niz od K zamjena pomoću kojih će on nizove učiniti jednakima.

Mirko ne želi izgubiti previše čarobne energije pa će biti sretniji što je K manji.

Zauzvrat, ako odradiš dobar posao, Mirko će ti možda pokloniti svoju zbirku čarolija.

Pozorno promotri sekciju BODOVANJE.

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 100 000), broj iz teksta zadatka.

U drugom retku nalazi se niz od N prirodnih brojeva, prvi niz iz teksta zadatka.

U trećem retku nalazi se niz od N prirodnih brojeva, drugi niz iz teksta zadatka.

Vrijednosti brojeva u oba niza bit će prirodni brojevi manji ili jednaki 100 000.

IZLAZNI PODATCI

U prvom retku ispiši nenegativan cijeli broj K (0 ≤ K ≤ 1 000 000), broj zamjena u vašem postupku.

U sljedećih K redaka ispiši po prirodna dva broja X (1 ≤ X ≤ N) i Y (1 ≤ Y ≤ N) koji opisuju zamjenu X tog broja iz prvog niza i Y-tog iz drugog niza.

Ulazni podaci bit će takvi da rješenje postoji.

PRIMJERI TEST PODATAKA

Ulaz

3
1 2 1
2 1 1

Izlaz

2
2 2
1 2

Ulaz

5
1 2 3 4 5
4 2 3 1 5

Izlaz

3
2 1
2 4
2 1

Objašnjenje

Ulaz

2
1 2
1 2

Izlaz

0