Gminmax

gminmax

== include(page="template/taskheader" task_id="gminmax") ==

Fie un graf neorientat cu $N$ noduri si $M$ muchii. Se cere un subgraf cu numar maxim de noduri, astfel incat gradul minim al unui nod din subgraf sa fie cat mai mare (gradul nodului se calculeaza in cadrul subgrafului si nu a intregului graf initial).

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $gminmax.in$ contine pe prima linie numerele $N$ si $M$ separate printr-un spatiu. Urmatoarele $M$ linii contin fiecare cate doua numere $x$ si $y$ reprezentand faptul ca intre $x$ si $y$ se afla o muchie.

Fişierul de intrare $gminmax.in$ ...

h2. Date de ieşire

Fisierul de iesire $gminmax.out$ va contine doua numere separate printr-un spatiu reprezentand gradul minim maxim ce se poate optine intr-un subgraf si dimensiunea maxima a unui subgraf care respecta aceasta proprietate.

În fişierul de ieşire $gminmax.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 500 000$
* Nu vor exista muchii duble sau muchii de la un nod la acelasi nod
 

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. gminmax.in |_. gminmax.out |

| 7 10
1 2
1 3
1 4
2 3
2 4
3 4
4 5
5 6
6 4
3 7
| 3 4

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Daca alegem subgraful format din nodurile $1, 2, 3$ si $4$ gradul minim al unui nod este 3. Nici un alt subgraf nu are gradul minim al unui nod mai mare ca 3 si acest subgraf este cel mai mare care respecta acest grad.

...

== include(page="template/taskfooter" task_id="gminmax") ==

3657