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)(N\; -\; 2)$ korda uus lamp ning ühendati see juhtmega mõne juba olemasoleva lambi külge. Tulemusena saadi ehe, milles on $NN$ värvilist lampi. Tehases on $KK$ 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 $MM$ 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 $NN$ ($2\le N\le 3000002\; \backslash le\; N\; \backslash le\; 300\backslash ,000$), kaunistusosakonnas tehtud asenduste arv $MM$ ($1\le M\le 3000001\; \backslash le\; M\; \backslash le\; 300\backslash ,000$) ja lampide võimalike värvide arv $KK$ ($1\le K\le {10}^{9}1\; \backslash le\; K\; \backslash le\; 10^9$).

Faili teisel real on $NN$ täisarvu $A_{i}A\_i$ ($1\le A_i\le K1\; \backslash le\; A\_i\; \backslash le\; K$), mis näitavad algse prototüübi lampide värve nende ehtesse lisamise järjekorras.

Faili kolmandal real on $N-2N\; -\; 2$ täisarvu $P_{i}P\_i$ ($1\le P_i\le i+11\; \backslash le\; P\_i\; \backslash le\; i\; +\; 1$), kus $P_{i}P\_i$ näitab, mitmenda lambi külge ühendati lamp number $(i+2)(i\; +\; 2)$.

Järgmisel $MM$ real on igaühel kaks täisarvu $X_{i}X\_i$ ja $Y_{i}Y\_i$ ($1\le X_i\le N1\; \backslash le\; X\_i\; \backslash le\; N$, $1\le Y_i\le K1\; \backslash le\; Y\_i\; \backslash le\; K$), mis näitavad, et $ii$. asendusel pandi lambi $X_{i}X\_i$ asemele lamp, mille värv on $Y_{i}Y\_i$.

출력

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

3 3 3
1 2 3
2
2 1
3 1
2 2

1
2
0

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

3