Fişierul intrare/ieşire:	tribes.in, tribes.out	Sursă	Algoritmiada 2017 Runda 2
Autor	Mihai Calancea	Adăugată de	Mihai Calancea •klamathix
Timp execuţie pe test	2 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tribes

In ce lume mai abstracta poti trai, decat intr-un graf neorientat cu N noduri si M muchii? Din pacate aceasta abstractizare nu te-a scapat de toate problemele lumesti. Locuitorii grafului s-au separat imediat in triburi, fiecare nod din cele N fiind membru al unuia din cele K triburi existente. Locuitorii grafului sunt foarte circumspecti in relatiile cu membri ai altor triburi decat cel din care fac parte. Un fel in care se manifesta aceasta prudenta este faptul ca un locuitor al nodului X care face parte din tribul T se va incumeta sa calatoreasca pana in nodul Y, de-asemenea parte din tribul T, daca si numai daca exista un drum intre X si Y cu proprietatea ca fiecare nod intermediar al drumului este fie din tribul T, fie vecin cu cel putin un nod din tribul T. O astfel de ruta este considerata sigura. Spunem ca doua noduri care fac parte din acelasi trib sunt conectate daca exista o ruta sigura intre ele. Numim o componenta conexa a tribului T o submultime maximala de noduri care fac parte din tribul T cu proprietatea ca oricare doua noduri din submultime sunt conectate, in sensul proaspat definit.

Se cere ca pentru fiecare trib dintre cele K sa afisati numarul de componente conexe in care este partitionat acesta.

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.

Date de ieşire

În fişierul de ieşire tribes.out se vor afla K linii, fiecare continand o singura valoare, a i-a dintre acestea reprezentand numarul de componente conexe in care este partitionat tribul cu numarul i.

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.

Exemplu

Cum se trimit solutii?