h2. Date de intrare

Fişierul de intrare $tribes.in$ va contine pe prima sa linie valorile $N M K$, reprezentand numarul de noduri ale grafului, numarul de muchii ale grafului, respectiv numarul de triburi. Urmeaza o linie cu $N$ valori intre $1$ si $K$, a $i$-a dintre aceste valori, fie ea $X$, semnificand faptul ca nodul cu numarul $i$ face parte din tribul cu numarul $X$. Urmeaza $M$ linii, fiecare continand o pereche de numere $U V$, cu semnificatia ca exista o muchie neorientata intre nodurile $U$ si $V$ in acest graf.

Fişierul de intrare $tribes.in$ va contine pe prima sa linie valorile $N M K$, reprezentand numarul de noduri ale grafului, numarul de muchii ale grafului, respectiv numarul de triburi prezente in graf. Urmeaza o linie cu $N$ valori intre $1$ si $K$, a $i$-a dintre aceste valori, fie ea $X$, semnificand faptul ca nodul cu numarul $i$ face parte din tribul cu numarul $X$. Urmeaza $M$ linii, fiecare continand o pereche de numere $U V$, cu semnificatia ca exista o muchie neorientata intre nodurile $U$ si $V$ in acest graf.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ K ≤ N ≤ 100.000$
* $1 ≤ M ≤ 150.000$
* Pentru teste in valoare de $30$ de puncte se respecta de-asemenea relatiile $N ≤ 1000$, respectiv $M ≤ 3000$.
* Din fiecare nod pleaca cel putin o muchie.
* Este posibil ca unele dintre cele $K$ triburi sa fie vide. Pentru aceste triburi raspunsul este $0$.
* Aceasta problema are feedback *complet*.

* $1 ≤ K ≤ N ≤ ...$
* $1 ≤ M ≤ ...$

h2. Exemplu