3. Technologická singularita

Vedcom z Krajiny Samých Pijanov sa podarilo vyvinúť teoretický model niečoho, čo nemožno nazvať počítačom, ani superpočítačom. Je to megapočítač. Keďže taký ohromný stroj by v nesprávnych rukách priniesol skazu a zánik ľudstva, profesor Einschwein sa rozhodol vziať všetku zodpovednosť na seba. Avšak jeho spolupracovníci postupne jeden po druhom mizli z povrchu zemského, až nakoniec profesor Einschwein ostal sám.

Devätnásteho septembra sa z Einschweina stal alkoholik, a to zmenilo jeho postoj k mnohým veciam. Uvedomil si, že taký superpočítač by sa mu vskutku hodil – stačilo by mu prikázať, nech ho spraví bohatým, a zo dňa na deň bude najbohatším človekom v Krajine Samých Pijanov. Mohol by sa nechať dosadiť na čelo vlády v každej krajine a byť vládcom sveta, zbaliť ľubovoľnú dievčinu, spýtať sa na veľkú otázku života, vesmíru a všetkého, a tak podobne…

A tak sa pustil do konštrukcie. Návod na konštrukciu mal nasledovnú formu:

1. zoberieme \(n\) súčiastok a \(n\) káblov. Súčiastky očíslujeme číslami \(1\) až \(n\).
2. pozapájame súčiastky do seba pomocou káblov. Zo súčiastky \(i\) bude viesť kábel do súčiastky \(A_i\), kde hodnoty \(A_i\) sú súčasťou návodu. Do každej súčiastky bude viesť jeden kábel, inak povedané postupnosť \(A\) je permutácia.
3. aplikujeme postupnosť výmen: pri každej výmene \(i,j\) prehodíme káble, ktoré vedú zo súčiastok \(i\) a \(j\). Pokiaľ pred výmenou viedli káble z \(i\) do \(x\) a z \(j\) do \(y\), tak po výmene budú viesť káble z \(i\) do \(y\) a z \(j\) do \(x\).
4. stroj zapneme, a…

…nič. Jasne si pamätal, ako zhotovoval návod, a pretože on chyby nerobí, určite niektorý jeho neschopný spolupracovník predĺžil návod o zbytočné a nefunkčné výmeny. Bohužiaľ, nepamätá si, aký dlhý bol pôvodný návod, ktorý zhotovil. Vie len to, že na konci vznikne práve jeden súvislý elektronický obvod – rád by preto vedel počet súvislých obvodov na začiatku a po každej výmene, aby zistil, kde všade jeho časť návodu mohla končiť.

Úloha

Dve súčiastky sa nachádzajú v jednom cykle, pokiaľ sa vieme po kábloch dostať od jednej ku druhej. Celý počítač sa skladá z niekoľkých takýchto cyklov (súvislých obvodov) a profesora Einschweina zaujíma z koľkých.

Daná je permutácia čísel \(A_1,A_2,\ldots,A_n\) popisujúca počiatočné zapojenie, a postupnosť \(q\) výmen súčiastok. Zistite počet cyklov v štandardnom zapojení, a po každej výmene.

Formát vstupu

Na prvom riadku vstupu sa nachádza prirodzené číslo \(n \geq 2\) — dĺžka permutácie. Za ním je v nasledujúcom riadku počiatočná permutácia čísel \(1,2,\ldots,n\).

Na treťom riadku je počet výmen \(q\). Nasleduje \(q\) riadkov, na každom z nich sú dve rôzne prirodzené čísla \(1 \leq i,j \leq n\), popisujúce výmenu káblov vedúcich zo súčiastok \(i\) a \(j\).

Formát výstupu

Na výstup by váš program mal vypísať \(q+1\) riadkov, na prvom z nich je počet cyklov v počiatočnej permutácii, a na ostatných \(q\) riadkoch je počet cyklov po príslušnom počte výmen.

Hodnotenie

Je 10 testovacích sád. V jednotlivých sadách platia nasledovné obmedzenia:

Navyše, v sadách 2 a 3 je počiatočná permutácia usporiadaná vzostupne.

Príklad

Input:

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

Output:

3
2
3
4

Input:

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

Output:

1
2
3
4
5

Input:

6
1 5 2 3 6 4
6
1 6
2 3
6 4
5 1
4 5
4 3

Output:

2
1
2
3
2
3
2