7165번 - Kuuseehe 다국어

문제

Byteland Party Factory valmistub uue kuuseehte turuletoomiseks. Selle prototüübi valmistamisel ühendati alguses kaks lampi juhtmega omavahel ja seejärel võeti $(N - 2)$ korda uus lamp ning ühendati see juhtmega mõne juba olemasoleva lambi külge. Tulemusena saadi ehe, milles on $N$ värvilist lampi. Tehases on $K$ eri värvi lampe.

Kui esimene prototüüp oli valmis, anti see üle kaunistusosakonnale. Seal otsustati, et ehte kauniduse mõõduks sobib kaht samavärvilist lampi ühendavate juhtmete arv. Seejärel vahetasid nad $M$ korda mõne olemasoleva lambi välja mõne teise vastu ja tahtsid iga kord teada, milline on saadud ehte kaunidus.

Kirjutada programm, mis saab ette ehte algse prototüübi ja kaunistusosakonna tehtud asenduste kirjeldused ning leiab ehte kõigi variantide kaunidused.

입력

Tekstifaili esimesel real on kolm täisarvu: ehtes olevate lampide arv $N$ (2ドル \le N \le 300,000円$), kaunistusosakonnas tehtud asenduste arv $M$ (1ドル \le M \le 300,000円$) ja lampide võimalike värvide arv $K$ (1ドル \le K \le 10^9$).

Faili teisel real on $N$ täisarvu $A_i$ (1ドル \le A_i \le K$), mis näitavad algse prototüübi lampide värve nende ehtesse lisamise järjekorras.

Faili kolmandal real on $N - 2$ täisarvu $P_i$ (1ドル \le P_i \le i + 1$), kus $P_i$ näitab, mitmenda lambi külge ühendati lamp number $(i + 2)$.

Järgmisel $M$ real on igaühel kaks täisarvu $X_i$ ja $Y_i$ (1ドル \le X_i \le N,ドル 1ドル \le Y_i \le K$), mis näitavad, et $i$. asendusel pandi lambi $X_i$ asemele lamp, mille värv on $Y_i$.

출력

Tekstifaili väljastada täpselt $M$ rida. Reale number $i$ väljastada $i$. vahetuse järgses konfiguratsioonis selliste lambipaaride arv, kus kaks samavärvilist lampi on juhtmega ühendatud.

제한

힌트