== include(page="template/taskheader" task_id="admitere-fmi-2016") ==

table{margin:0.5em auto;}. |={background-color:#c4baf8;}. !<template/admitere-fmi?study2.png! '*Versiunea originală*':http://fmi.unibuc.ro/ro/pdf/2016/admitere/licenta/Subiecte_DL_INFO_iulie_2016.pdf _a acestei probleme a fost propusă în cadrul examenului de admitere al_ '*Facultăţii de Matematică şi Informatică, Universitatea din Bucureşti*':http://fmi.unibuc.ro/ro/.
_Versiunea de faţă este publicată cu permisiunea organizatorilor examenului, dar aceştia *nu* sunt responsabili pentru modificările aduse problemei în scopul adaptării la contextul evaluării automate. Rezolvarea acestei probleme *poate diferi substanţial* de experienţa examenului real. În particular, punctajul obţinut pe această problemă *nu* poate fi corelat cu notarea oficială. Informaţii oficiale despre examenul de admitere al Facultăţii de Matematică şi Informatică, cât şi despre pregătiri oficiale pentru examen se pot găsi_ '*aici*':http://fmi.unibuc.ro/ro/admitere_licenta/examen_admitere_iulie_2020/. |
 

Ionuţ tocmai a terminat liceul şi susţine examenul de admitere la facultate. Ştiind că s-a pregătit foarte bine pentru examen, el doreşte să îşi anunţe reuşita după examen printr-o postare pe Facebook. Ionuţ cunoaşte _n_ utilizatori reprezentaţi de numerele de la 1 la _n_, între care există _m_ relaţii de prietenie de forma _i j_, unde _i_ şi _j_ sunt utilizatori, iar _n_ şi _m_ sunt numere naturale nenule. Un utilizator nu poate fi prieten cu el însuşi, iar o relaţie de prietenie între doi utilizatori ne spune că fiecare dintre ei este prieten cu celălalt.
Întrucât doreşte ca postarea lui să fie cât mai răspândită, Ionuţ vrea să afle care sunt utilizatorii cei mai bine conectaţi din mulţimea sa de cunoscuţi, pentru ca eventual să le ceară prietenia. Pentru aceasta, Ionuţ trebuie să găsească cea mai mare submulţime de utilizatori cunoscuţi, în care fiecare utilizator din această submulţime are cel puţin _k_ prieteni aflaţi la rândul lor în submulţime, unde _k_ este un număr natural nenul.

a) Să se determine şi să se afişeze, în ordine de la 1 la _n_, numărul de prieteni al fiecăruia dintre cei _n_ utilizatori, conform relaţiilor de prietenie date.
b) Să se determine şi să se afişeze, printr-o soluţie de complexitate timp cât mai bună, în funcţie de datele de intrare, membrii celei mai mari submulţimi de utilizatori, cu proprietatea că fiecare utilizator din această submulţime are cel puţin _k_ prieteni aflaţi la rândul lor în submulţime. În cazul în care nu există o astfel de submulţime pentru _k_ dat, răspunsul va fi cuvântul $NU$.

h3. Disclaimer
 
Această problemă este publicată cu scopul de a-i ajuta pe elevi să se pregătească pentru admitere. Facultatea nu îşi asumă nicio răspundere cu privire la corectitudinea acestei probleme. Singura sursă oficială de informaţii cu privire la admitere este 'site-ul facultăţii':http://fmi.unibuc.ro/.
 

h2. Date de intrare
Fişierul de intrare $admitere-fmi-2016.in$ conţine numerele _n_, _m_ şi _k_, pe aceeaşi linie, separate prin spaţiu, precum şi _2m_ numere naturale cuprinse între 1 şi _n_, pe o linie nouă, separate prin spaţiu, reprezentând în ordine cele _m_ relaţii de prietenie între cei _n_ utilizatori.

* $1 ≤ n ≤ 100.000$
* $1 ≤ m ≤ 200.000$

* $1 ≤ k ≤ n$

* $1 ≤ k < n$
* Nu se iau în considerare submulţimile formate dintr-un singur utilizator cu _k_ prieteni.

h2. Exemplu