Finalizăm trilogia MVC de anul acesta prin următoarea problemă: Fie un graf $G$ cu $N$ noduri şi $M$ muchii. Numim acoperire cu noduri a grafului o mulţime de noduri $A$ cu proprietatea că orice muchie din graf are cel puţin unul din capete situat in mulţimea $A$. În această problemă trebuie să găsiţi o acoperire cu noduri a grafului $G$ de cardinal minim.

Se garantează ca pentru grafurile date în input, există o acoperire de noduri cu dimensiune maxim $18$.

Se garantează ca pentru grafurile date în input, există o acoperire de noduri cu dimensiune maxim $20$.

h2. Date de intrare

Fişierul de intrare $rmvc.in$ conţine pe prima sa linie numerele $N$ şi $M$ semnificând numărul de noduri şi numărul de muchii ale grafului. Următoarele $M$ muchii conţin câte o pereche $x y$ semnificând că există o muchie între nodul $x$ şi nodul $y$. Se garantează că nu există muchii cu capetele în acelaşi nod, însă pot exista muchii duble.

Fişierul de intrare $rmvc.in$ conţine pe prima sa linie numerele $N$ şi $M$ semnificând numărul de noduri şi numărul de muchii ale grafului. Următoarele $M$ muchii conţin câte o pereche $x y$ semnificând că există o muchie între nodul $x$ şi nodul $y$. Se garantează că nu există muchii duble sau muchii cu capetele în acelaşi nod.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ N ≤ 90$
* $1 ≤ M ≤ 320$

* $1 ≤ N ≤ 60$
* $1 ≤ M ≤ 190$

h2. Exemplu

3 4 2
|

h3. Explicaţie
 
...
 

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