Count

count

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

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

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.

Poveste ...

h2. Cerinta

Fiind dat un graf planar aflati cele doua numere cautate.

...

h2. Date de Intrare

h2. Restrictii

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 Iesire

h2. Date de intrare

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. Restrictii si precizari

h2. Date de iesire

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

...

h2. Exemplu

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 |

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

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")==
 
 

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

795