Fişierul intrare/ieşire:dmin2.in, dmin2.outSursăAlgoritmiada 2013, Runda 2
AutorAndrei GrigoreanAdăugată deGheorgheMihaiMihai Gheorghe GheorgheMihai
Timp execuţie pe test0.07 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dmin2

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.

Date de intrare

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.

Date de ieşire

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

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.

Exemplu

dmin2.indmin2.out
5 3
1 2
2 3
3 5
3

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?