dmin2

Dmin2

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

Poveste şi cerinţă...

Pentru a ajunge la casa bunicii, Scufita Rosie trebuie sa traverseze Padurea Luminoasa. In padure exista $N$ luminisuri (pentru simplitate vom considera ca initial Scufita Rosie este in luminisul $1$ si casa bunicii este in luminisul $N$). Luminisurile sunt legate intre ele prin $M$ poteci, iar Scufita se poate deplasa doar pe poteci si prin luminisuri (altfel o va manca Lupul cel Mare si Rau). Stim ca orice drum ar alege fetita, ea va vizita cel putin $4$ luminisuri pentru a ajunge la casa bunicii (incluzand luminisurile $1$ si $N$).
 
Pentru a o ajuta pe Scufita sa nu se rataceasca, Padurarul cel Viteaz vrea sa amenajeze cat mai multe **poteci noi** prin padure, dar vrea sa construiasca potecile in asa fel incat orice drum ar alege fetita, ea sa viziteze cel putin $4$ luminisuri.
 
Ajutati-l pe padurar sa creeze un numar **maxim** de noi poteci astfel incat mergand prin padure, Scufita sa viziteze cel putin $4$ luminisuri.

h2. Date de intrare

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

Fişierul de intrare $dmin2.in$ contine pe prima linie numarul doua numere naturale $N$ si $M$ cu semnificatia din enunt. Pe fiecare dintre urmatoarele $M$ linii se va gasi cate o pereche de numere $x$ si $y$ cu semnificatia ca exista o poteca intre poiana $x$ si poiana $y$.

h2. Date de ieşire

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

În fişierul de ieşire $dmin2.out$ scrieti numarul maxim de poteci pe care le poate amenaja padurarul!

h2. Restricţii

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

* $1 ≤ N ≤ 100000$
* $1 ≤ M ≤ 300000$
* Vom considera ca doua poteci se vor intersecta doar intr-un luminis.
* Intre doua luminisuri va exista cel mult o poteca.
* Stim ca Scufita poate sa ajunga la casa bunicii folosind cele $M$ poteci initiale.

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

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

| 5 3
1 2
2 3
3 5
| 3

|
h3. Explicaţie

...

Padurarul va amenaja poteci intre $2$ si $4$, $3$ si $4$ si $4$ si $5$.

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