dmin2

Dmin2

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

Pentru a ajunge la casa bunicii, Scufita Rosie trebuie sa traverseze Padurea Bucuroasa. In padure exista $N$ luminisuri (pentru simplitate vom considera ca 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 Scufita, ea va vizita cel putin $4$ luminisuri pentru a ajunge la casa bunicii (incluzand luminisurile $1$ si $N$).

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, Padurarul cel Viteaz vrea sa faca cat mai multe **poteci noi** prin padure astfel incat Scufita sa ajunga cat mai repede la casa bunicii, dar totusi vrea ca orice drum ar alege aceasta, sa viziteze cel putin $4$ poieni (altfel fetita ar manca din prajiturile bunicii si nu ar mai admira frumusetile padurii).

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$ poieni.

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

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