count

Count

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

==Include(page="template/taskheader" task_id="count")==

Poveste ...

Fiind dat un graf planar cu $N$ noduri si $M$ muchii aflati numarul maxim de noduri pe care il poate avea un subgraf complet al sau (un graf neorientat se numeste complet daca exista muchie intre oricare doua noduri ale sale). De asemenea se cere si numarul de subgrafuri complete cu numar maxim de noduri care se gasesc in graful planar dat.

h2. Cerinta

...

Fiind dat un graf planar aflati cele doua numere cautate.

h2. Restrictii

h2. Date de Intrare

...

Linia 1 a fisierului de intrare contine doua numere naturale separate prin spatii $N$ si $M$ (numarul de noduri, respectiv numarul de muchii ale grafului planar).
Liniile $2 .. M + 1$ contin cate doua numere $A$ si $B$ cu semnificatia: exista o muchie bidirectionala intre nodurile $A$ si $B$ (nodurile grafului sunt numerotate de la $1$ la $N$).

h2. Date de intrare

h2. Date de Iesire

...

Fisierul de iesire va contine pe prima linie doua numere $X$ si $Y$ reprezentand numarul maxim de noduri pe care il poate avea un subgraf complet si, respectiv, numarul de subgrafuri complete cu $X$ noduri din graful planar dat.

h2. Date de iesire

h2. Restrictii si precizari

...

* $2 ≤ N ≤ 30 000$
* $1 ≤ M ≤ 60 000$
* $Y ≤ 2^30$
* Pentru $70%$ din teste $N ≤ 2000$

h2. Exemplu

| count.in | count.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. count.in |_. count.out |
| 5 8
1 2
1 3
1 5
2 4
2 5
3 4
3 5
4 5
| 3 4 |

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

h3. Explicatii
 
Se pot forma 4 subgrafuri complete cu 3 noduri. Acestea sunt:
(1 2 5), (2 4 5), (3 4 5), (1 3 5)
 
==Include(page="template/taskfooter" task_id="count")==
 
 

795